I thought of recommending the North Rim of the Grand Canyon but for a first-time visitor I think the South Rim is better. Besides, he's coming from Sedona. You see more of the canyon from the South Rim. We've done the South Rim a few times but now go to the North Rim for the quietness. The North Rim is a good option though and it's pleasantly cool.
The Grand Canyon South Rim will be hot, just like the Sedona area. It's high desert. Bryce Nat'l Park and Flagstaff will be the coolest places on this trip. Arizona has many different levels of temperature. That's why we enjoy it so much. You can always find a place to warm up or cool down.