SE Utah is one of my favorite areas - I go as often as I can, and it's never ever enough. I was there in December (cold and windy) - spring is much nicer.
If you decide to take a detour through the San Juans - beware the roads. Check out road conditions - the road between Telluride and Moab is narrow, windy, and may be closed if snow conditions exist. Beautiful, but beware. If you decide to to on this type of detour, Gateway is also an option - beautiful canyon/river areas as well.
And, while you're out walking around, don't forget to look down. The potholes, especially in Arches and Canyonlands, can be absolutely fabulous. A whole ecosystem in miniature.
Good advice to take 128 in as well - the view of Fisher Towers from the edge of the Colorado River is wonderful; got some nice winter reflections when last there.