When the cities are too far apart, or we decide to skip big places like Nizhny Novgorod, despite the temptation to be able to say it, we either camp in a forest or find a Гостиница (gostinitza/hotel) along the road.
For 500 roubles per person (about $AU12) we get 3 twin rooms, thereby half filling the place, and it is spotless. The rooms, the cafe, the showers, toilets, the handbasins used by the truckies, all of it, spotless. The staff constantly mopping and cleaning, the kitchen staff washing hands and wiping down benches, no sign of mud tracked through, and the truckies from their truck-cab beds, carefully shaving, teeth cleaning, and wiping down the basins.
We ate well, had a few beers and a laugh in the busy, friendly cafe. The whole night cost us one tenth what we had paid in the big city hotel the night before.