I've been out to Mormon Country 3 times in the past 2 years; I've become addicted to red rock.
I've been to 3 National Parks there:
Go to Arches and do yourself a favor by hiking in to some of the lesser known arches in the Park; the loop road does not do the park justice. (Watch out for Winnebagos)
Canyonlands is not as popular as some of the others, but the scenery and desolation are spectacular. If you're looking to avoid crowds I'd recommend this one.
Zion has any number of great hikes around and through the canyon. Some of the trails are a steep climb and involve chain handrails, others bisect the park. I didn't hike the Narrows because I didn't have enough time, but I wish I had. If it is solitude you seek, go to the Kolob Canyon section of the park (it's not connected to the main part of the park) and hike around.
Other recommendations:
Natural Bridges National Monument, west of Blanding. There's a great 20 mile loop hike under some of the bridges if you have time.
Muley Point on Cedar Mesa. Incredible views of wasteland in every direction. Some dirt road driving. Take the Mokee Dugway (State Route 261). It puts the Mt. Washington Auto Road to shame because it literally hugs to the side of a sheer cliff. Scary. Not for the faint of heart or faint of driving skill. I loved it.
Goosenecks State Park, below Cedar Mesa. Its worth seeing briefly, there's not much to do there but look.
San Rafael Swell Wilderness Area. This one was my favorite. You drive through Utah on I-70 you pass through the area. Its better to take dirt roads in and visit the east face of the swell; nude Navajo Sandstone, you can't miss it. Explore up and down the east face of the swell, there are a ton of side canyons that lead up into the guts of it, and many of these contain ancient cliff dwellings. Hardly anyone visits this area.