Many good suggestions here, with higher elevation as the common thread.
Consider exploring valley floors early in the day then heading uphill as the temperature rises. Some of the areas mentioned in earlier posts are around 10,000 feet and will be nice and cool for camping, even chilly at night.
Similar places not yet mentioned include Lava Point up above Zion NP, Cedar Breaks National Monument, and the Henry Mountains east of Capitol Reef NP.
It's still too early to tell, but extended forecasts say we may get more of a monsoon this summer than the past couple years. We could sure use the rainfall and it would definitely cool things down on the desert. Just be careful of flash floods across roads and when choosing camp spots. Also, from my experience, you can believe it when the Benchmark atlas marks a road as Impassable When Wet.
Be safe and have a great trip!