Duke48 - Just to be clear. I think most would recommend reservations for those mentioned big holidays. For example, 4th of July. Take a look at your projected general course, add a few days for both contingency and 'Gee, let's stay here a bit longer!' - and eye ball where you think you'll before the 4th's holiday. Choose a spot where you'd like to hunker down, and then get reservations for that.
For example, we leaver from Southern California in mid May. Going to the 100th running of the Indy 500, then on up into Maine before running back West along along the Great Lakes and South of the Canadian border. As of now, we have three reservations. I call these 'Anchor Point' reservations. Knowing that I want to hit the park for Indy on the Friday before the 500 race. In Maine, yep, a 4th of July reservation at another 'Anchor Point'... In between all of these, we just take our time, as I leave plenty of time in the schedule for weather, problems, and fun changes in schedule.
We too usually start calling around noon, to a few parks in the area we feel we want to stop at between 2:00-3:00PM. Some say no problem, no reservation needed. Others say sure, lets make sure you have a space.
You guys will get a system going that works for you.
Have a blast. Oh, and I agree with the comment about a bit warm that time of year in New Mexico, AZ and UT - depending on elevations. Perhaps think about wandering North from your few States, and then back down and around the hotter states later in your travels. (If you will be out that long. Say September and October, and you should find less crowds, and cooler temps too
Best to you,