What Josh said about the Northern Tier. Wet weather wise, I would wait until at least mid-June and possibly later, especially if you go that route. The first two times I rode the NT it was chilly and damp in places like Sandoint, ID and Eureka, MT and Whitefish, MT in early to mid-June. In 2009 I rode from Whitefish through Eureka to the Canadian Border in the 3rd week of June. Same thing. Chilly and drizzly off and on.
Also, while frontage roads often exist, they don't always exist, so you might find yourself on the Interstate. Sometimes the frontage road on one side of the Interstate abruptly ends with no way to enter the highway, requuring you to backtrack to a point where you can cross over the highway and continue on the frontage road on the other side. This can require careful planning to avoid such situations. Finally, not all frontage roads are paved.