I think underwater is both immersive and under-used...

Above the clouds. That's good stuff. I think it's used in platformers (Mario anyone?) quite frequently but not so often in an RPG-like setting.

I've always been a big fan of the steampunk factory/clockworks setting - the Esper Research Facility from Final Fantasy VI springs immediately to mind as the best example, as well as the clock tower areas in the Castlevania series.

I'm a whore for bridges, or bridge-like structures.

Let me run atop a massive, ancient, crumbling aqueduct and you've given me my new favorite game.

I really enjoy well-designed forests with rivers.

If there is a lot of wildlife( foxes,birds,fishes...) too, you can make me happy.

And some awesome ambient background sounds are important, too.

Good point about forests.

I grew up near woods and wandered them on occasion. The level of detail needed to really capture a forest is tough. I'm not even sure how games would handle moving through underbrush, getting caught on thorns and branches, etc. The feeling of really being in a forest is much different than the way it's done in any video game I've played.

Huge artificial gardens (Like the hanging gardens of babylon)

Underground streams

Crystal caves (or dungeons, Dark Environment + Huge Crystals is always nice)

Misty forests (or misty caves, thats nice too)

Inside of a huge overgrown temple

Lava cave (but only if executed right)

Dark City , the timeframe does not even matter as long as it has dark an twisted alleyways and dead ends.

@Clint Bellanger: Me too, but in my opinion a game can never give you the same feel as real life.

Game is fiction and therefore you should can do there things which you can't do in reality.

Not the reality of a game is important, but the ambience is.