*edit* sorry, i was typing all that while you guys were replying...
If you're in to wheeling and she's in to hiking, try this route...start in Moab, drive north til you get to Klondike Bluffs road. Drive up to the Bluffs (dont miss the dinosaur footprints along the way, particularly the mass of footprints down the wash to the left when you cross the big crack), hike out to the end of the limestone cap and look out at the red rocks below. There is a dinosaur footprint waaaaaay out on the end, you have to be brave and athletic to reach it. As long as it's not raining, drive back but TURN RIGHT at the T near the top instead of turning left and going back down. If the route looks too chunky, head back down Klondike Bluffs road, however we did get a stock Tundra through. It's some ledges, narrow stuff, big rocks, and other things that will eat your sheetmetal and low-hanging fruit if you're not careful, but it's very short. Anyway, after the right turn, head up and over the ridge line...just go straight at the top...watch out for the ledges on the switchbacks on the way down, and it's narrow, but remember a Tundra went through there. At the bottom, continue straight to meet Salt Valley Road. You're outside the Nat'l Park, so you can camp anywhere you want. SVR enters Arches Nat'l Park land, there's a sign so you know which side you can camp on. Continue on SVR to the Tower Arch 4wd trail turnoff. It's a right hand turn leading back toward the ridge line...you cross it again but this time in the red rock, not the white limestone. It's chunky over the ridge and sand everywhere else. This is a good place to check the weather if you havent already...the trail is impassable when wet, as you're mostly driving down a sandy wash. You can park near Tower Arch, hike to the arch and the double arch to the right, and hike the primitive trail (it's beautiful) back to the Salt Valley Road if you like. Look for the "broken" arch on the right in the valley.
Coming out, make a right turn on 4WD road, again this is an "impassable when wet" road mostly on soft sand, so don't tread here without low pressure, oba, recovery ladders, 2nd vehicle if possible, etc...follow 4WD road out to Eye of the Whale arch and eventually to the main road in Arches Nat'l Park right by Balanced Rock.
You can do it in a day, but you'll be rushed...better to enjoy the hiking and camp outside the park in Salt Valley.
Needles District is also a great area for hiking and 4WD, and you can reserve campsites in the Grabens (Elephant Hill). Don't mess with Elephant Hill unless the weather is clear and you have a 2nd vehicle+fullsize spares+recovery gear OR you're extremely well equipped and an experienced driver. We did bring the same stock Tundra through the loop, he received some body damage during an unspotted section. I did not take damage, but we almost lost the Pinzgauer, the rental Jeep had rubbing issues, and the stock Jeep tore a sidewall and took damage. Elephant Hill is mostly a driver skill issue, and slightly weather dependent. Camping is available at the 2WD parking lot, Squaw Flat, you can hike from there, it's a beautiful place.
North of Moab, the Old Stage MTB/Hiking loop is really beautiful. So is Moab Rim, Slickrock Trail, and of course Devil's Garden but it's full of tourists
...maybe not so much this time of year. You can also hike the Cliffhanger/Amasa Back multi-use trail...take Kane Creek road west out of Moab (there are a couple fast food joints on the corner, like a BK or something) and park at the Amasa Back parking area, hike up the road and look to the right for an impassable-looking, chunky, ledge-ridden slickrock pile leading downhill. The views from the trail are incredible, you can see Behind the Rocks WSA from the front, the river on one side and the evap ponds on the other from the top. On foot, it's easy. By MTB, it's a ton of fun. In 4WD, obstacles range from Difficult to Poop Yourself depending on your line.
The Gemini Bridges area does have a road leading to the river, and is generally fairly easy with hiking on the side. Hey Joe Canyon is next to the river and leads to an old uranium mine.
FYI Potash Road is a washboarded mess. Avoid it.
Canyonlands Reservations 435 259 4351 (Gary and Bruce are very helpful)
Needles Visitor Center 435 259 4711 (they'll have current weather info)
That's all the info I have at the moment...pick up a couple Natl Geo maps from REI or somewhere, or a couple of the extremely detailed, high quality maps sold everywhere in Moab...there's a Moab North and Moab South version, they list everything, and the Park visitor centers are very helpful.
If you have time, Fiery Furnace is a great day hike, but you gotta sign up in advance for the guided tour if you haven't been in before. I highly recommend the furnace, your girl will love it.
What days do you plan on being there--any weekends? If you'd like company and it's on/near a weekend, we might be able to head over for a day or two, it's only 4 hours from Denver.
There's a book by I think HG Wells, called Utah 4WD and Backcountry Roads, and another (I forget the author) about 4WD and hiking trails in Utah.
-Sean