I've done close to that route in spring (April) through the big rocks, but I would never have done so without taking a mountain flying course first. I also had several alternate routes planned for weather. Here was the trip out:
KHND plus a rental car was cheaper than the fees at KLAS.
With this sort of thing, I would plan multiple routes, and not return the same way you came. Definitely take a detour to Sedona for a meal, that's a memorable stop and one of the best airport restaurants I've ever encountered. Bryce Canyon is also spectacular; I've stopped for a meal there (IIRC they have a courtesy car but only available when the FBO is open) and then made it an overnight.
An easier route farther to the north is 06C CKW HVE KBCE VPGCB VPGCA CUNDY KHND, that also gets you over Bryce Canyon and the Grand Canyon (be sure you review the procedures for Grand Canyon flying, make sure you have the chart downloaded, and DO IT!).
A good southern route would be 06C LVS RENCO ADABY KSEZ KHND, that will get you to Sedona. You could do the Grand Canyon on this one too.
As far as what's in between... Well, there used to be a nice little restaurant at KOFK Norfolk, NE but I'm pretty sure it's gone unless someone decided to open it back up. Otherwise, there's a whole lotta nothin'. Pack a lunch and keep flying. If you do decide to tangle with the big rocks, there's an excellent restaurant at KAPA, The Perfect Landing. Sedona, as mentioned.
If you end up wanting to RON in the Denver area, KCFO Colorado Air and Space Port (formerly KFTG Front Range) has always provided fantastic service to me. They're not right in town, but there's no traffic between you and the hotels, fantastic service, and cheap self serve fuel. They do have a restaurant on field there too (again, check if it's still open... Sigh).
Were I you, I'd take the northern route one way, the southern route the other way. Probably west and east, respectively, keeping in mind that the southern route gets some bad turbulence so you'll not generally want to go through there in the afternoon.
Have a great trip!