I've got 2 LAX-ORD-CDG-AUH-MLE-AUH-CDG-JFK-LIH tickets on hold with AA, and the CDG-AUH-MLE-AUH-CDG flights are on Etihad. The CDG-AUH-MLE connection leaves us (wife and I) in Abu Dhabi from 8:40PM to 9:20AM, so I've got a few questions.
1. Is it worth the hassle of obtaining a visa to leave the airport for 12h?
2. Assuming the answer to 1 is "yes," what can we accomplish overnight in Abu Dhabi?
3. Is there any time for a trip up to Dubai? I ask because I've never been to the Middle East, and don't know if I'll be there again.
4. Assuming we stay the night in Abu Dhabi (though I'm not opposed to staying in Dubai), what are some good choices? I'd like to spend less than 600 AED, since it's only a 12h stay, but can make some exceptions for exceptional circumstances.
The timings of your arrival do limit somewhat what you can do.
1. Many nations get a visa on arrival, which takes no time at all. If you are one of these, there isn't much hassle to worry about
2. Like I said, the timing isn't great, but you could go out clubbing at the Emirates Palace or on Yas Island. Or just go for dinner, then a stroll down the Corniche (if you're there at a weekend you may be suprised by the amount of people on the Corniche at all hours of the night).
3. From Abu Dhabi airport to the southern end of Dubai is probably about a 45 minute car journey. You might find a few more nightclubs and restaurant choices, but otherwise same issue with the timing as Dubai.
4. Why don't you look at Booking.com for hotels in your price range and then post a few names and I can tell you what they're like?
Le Royal Meridien looks like it's having a pretty sweet deal right now: 410 AED for the night.
I know absolutely nothing about Abu Dhabi, but I think I'd prefer downtown to Yas Island. I think, as has been suggested, we'll have dinner, grab some drinks (clubbing isn't our thing), take a stroll along the Corniche, and dip our toes in the Gulf.
csdf, since you're an Abu Dhabi local, could you share some of your favorate moderately-priced restaurants and/or bars (either itt or via PM)?
If you want to drink alcoholic drinks, then your choice of restaurants is limited to hotel ones, of which there are plenty, but they're expensive. For instance, last week a bowl of mussels, a plate of meatballs, 2 beers and a glass of wine at the Belgian Beer Cafe  (Intercontinental hotel: nice place with outdoor seating and live music on Fridays) cost me about 500 dhs. Also last week, one shared starter and two main courses, together with 3 glasses of wine at Certo (don't even think of going - it's awful) cost me 380 dhs.
If you're not bothered about alcohol, then the city offers you a gazillion local restaurants, serving mostly the indian, pakistani and lebanese expatriate community, where you can eat a full meal for 30-50 dhs. One good place you could try is the Lebanese Flower, which is a touch more expensive (50-90 dhs). There's a branch  near Al Wahda mall on 11th (any taxi driver will know where it is, but it's 10 minutes from the Corniche) with outdoor seating and the chance to witness countless Emiratis rock up in their LandCruisers and honk the horn for drive-through shawarmas. There's another branch somewhere in Khalidiyah which I've never been to.
Or you could try Vasco's  at the Hilton Beach Club, which is on the Corniche and has a good mix of food but is hotel-based so more expensive.
Or for good local flavour combined with great views, try Le Boulanger  (lebanese food) on the Marina Causeway: if you can find a spare table outside it's well worth it.
For swank with service, Hakkasan in the Emirates Palace is excellent if pricey. 
For a cracking but expensive Indian, there's Ushna at the Souk , or the excellent, pricey and sadly often empty Bord Eau at the Shangri La 
Decent bars (all will be pricey, as alcohol is heavily taxed):
* Relax @ 12 at Aloft hotel (rooftop views but in a dull part of town)
* The Skybar at the Yas Hotel (swanky and rooftop-but-not)
* Belgian Beer Cafe at the Intercontinental
* Hemingways at the Hilton (sport, beer swigging)
* Pool Bar at the Shangri-La (view of Sheikh Zayed Mosque, nice outdoor atmosphere)
Sheraton was once on the Corniche, but then they moved the Corniche so now it's set back, with a remnant "beach" but a massive 6 line highway beyond that and the new Corniche. I've been to a couple of the restaurants and bars and they were fairly rustic.
Beach Rotana has good restaurants (e.g. Pregos, Finns) but the beach now looks over the creek onto a major construction site.