RP, you may have found these already, but just in case here's links to online bicycle maps for Washington/Oregon/Montana/Idaho, that may help with route planning:
Oregon & Washington:
There's paved rail/trails called the Centennial Trail / Trail of the Couer D'Alenes)
they run pretty much the whole way from Spokane to the Montana border, so that might make for an interesting route. Have heard good things about them.