Exploration as gameplay element is one of my favorite things, especially in RPGs, and especially first and third person ones. Gothic 2 would be my favorite choice as well, along with their other games (the first Gothic, and Risen).
The Ultima Underworld games were fantastic examples of this back in their day. In some respects they’ve yet to be surpassed, especially in the way they evoked the best pnp roll(role ;-) playing experiences I had as a kid. I’d pay a lot to have one game along these lines every year. A lot! ;-)
System Shock 1+2. Loved both these games. Dangerous, slightly puzzly dungeon crawl to work through with fantastic atmosphere and a ton of diverse challenges.
Despite the mediocre to poor combat and uneven design decisions across the series, the Elder Scrolls games have many high points.
The original Everquest blew my mind when it came out - the combination of tension and fear of the unknown was incredible. Making that run through the minotaur patrolled canyon that connected the two coasts for the first time is one of the most memorable gaming experiences I’ve had. Ditto accidentally finding, exploring, and ultimately dying in Paw (? the one off in the midst of a plain far from the beaten track) dungeon.
Many other MMORPG’s have worked for me on a similar level, though increasingly less so than Everquest did. I loved scoping out the original WoW especially though. Diverse, large, imaginative, colorful, and with a sense of fun, WoW was the most rewarding of the MMORPGs in terms of exploration.
As others have mentioned, Just Cause 2 is great - the world is vast, beautiful, and densely populated with opportunities for adventure. It’s a little shallow, but perfect for ‘I have 20 minutes to get in some fun’ gaming now and then. I really wish someone could take this engine and make an elder scrolls style game with it.
Demon Souls - fantastic, creepy world to wander in. A bit punishing and grindy/repetitive, but still, fantastic atmosphere and super challenging bosses as the ‘reward’ for exploration.