I forgot to mention there are a couple of really nice trails out west. The Mickelson Trail (about 100 miles) in South Dakota. The surrounding area is an outstanding area to ride including Mount Rushmore and Custer State Park.
Another noteworthy trail is short (15 miles) but fantastic. It is the Route of the Hiawatha (RoH). It goes through 10 tunnels (one 1.6 miles long and you must have at least a flashlight) and over 7 really high old-time wooden train trestles. Downside is it costs $11. If you are actually riding through on a coast to coast option, I would suggest riding to St Regis, MT, then take National Forest Road (NF) 282 (gravel) over the mountain pass to NF-388 (paved). At bottom, turn right onto NF-50 (paved) along the stunningly beautiful St. Jo River to Avery, ID. Then go uphill (gravel) to the southern end of the RoH and begin the RoH. One done with it, continue to to I-90 where you can get on the gravel trail west to Mullan, ID. From there, take a paved rail trail to Spokane, WA. NOTE: The route between St. Regis and Avery has low traffic and NO services except Forest Service campgrounds, some with hand-pump water, so be prepared.
If you end up doing this, contact me privately and I will try to get you my cue sheets and/or GPS routes.