I just noticed you're going to be riding 89 southeast of Great Falls. One of my favourite places to stay is Bob's Motel in Neihart, in the Lewis and Clark Forest. It's pretty basic, with reasonable rates, but it has a nice bar on the lower level, where all the locals go to hang out - a very interesting place.

If it's raining, Tony, the owner, will let you park under the staircase, around the back.