Utah is accessible from Vegas, and you get cheap rental cars in Vegas and cheap flights, often as not. Salt Lake is the other obvious option.
Zion NP is one of my favorites, but a lot of Utah LOOKS like it should be a national park and is just land.
We hit this area in late September one year. We stopped at one little church for the wife and just outside the church in the middle of town was a moose and her kid, whatever a baby moose is called, chowing on some foliage. This was near Park City, another small town in the area. The moose was quite placid though I gave it appropriate berth.