Flagstaff is indeed beautiful and cooler, as is the “Rim” country northeast of Phoenix. As you go north, elevation increases, and Flag is around 7,000 ft. You can climb 12,600-ft Humphries Peak if you are so inclined.
From Flag you can drive through the Painted Desert or on up to Lake Powell and take boat rides there. Also, the North Rim of the Grand Canyon is wonderful, but if you don’t have time (it’s hard to get to), any and all parts of the South Rim are spectacular. Just don’t climb down, as it gets much hotter at the bottom.
Sedona is still beautiful and an astonishing place, but be warned, they have just recovered from a terrible wildfire NW of the town and many of the hiking trails are nothing but burned land now. Still worth seeing the red rocks. No matter how many pictures or films you’ve seen of them, it’ll knock your eye out when you behold them in person.