Has anyone mentioned Aquaria yet? I personally loved the exploration aspect of it.
For those who don't know, Aquaria (http://www.bit-blot.com/aquaria/) is an indie title whose genre I guess could be described as 2D action-adventure, with very light RPG elements in the mix (You can use bits dropped from critters you kill to cook and make powerup foods, you can find outfits with helpful effects, and you can find health upgrades. That about covers the RPG aspect.)
Anyway, you play as an amnesiac mermaid (it's not as bad as it sounds!), Naija, searching through the ocean for her origin and for other sentient species. The environment in the beginning level seems pretty restrained. A few side things if you look around a bit, but primarily just temple 1 and temple 2. After those, you can finally advance out of that area.
The true open ocean floored me quite quickly. Even though Naija provides pretty broad hints of where to go next plotwise, the game makes very little effort to prevent you going an entirely different direction. A healthy slice of the entire game world's open for viewing even when you have only the two powers you obtained from the beginning.
But I'll carry on for a long while if I don't close off soon. Aquaria doesn't have quite the silent beauty of SotC, but it definitely has the loneliness. The way I say it makes it sound like a bad thing, but I mean it in the best way possible. Only a few sentient beings do actually reside in the world (semi-spoiler, but you get that impression pretty early in anyway). And I've noticed all the people with distaste for maps, fear not! The minimap only displays the structure of the land, and the main map only labels things after you find them.
I truly feel this game exemplifies exploration like the others you all have mentioned, with its vast and quite stunningly beautiful seascape.
Okay, okay, I'm done now.