True enough, and meaningful exploration is my favorite thing in the gaming universe.
That's a strong reason I can never REALLY get into MMOs, because they have to limit that aspect severely, due to balance concerns.
There's nothing like coming across a cave, giving you the sensation that you're the first one there in a LONG time - and getting a nice sense of immersion based on scraps of paper and a bit of loot. So few games get this relatively simple thing right.
They need to look towards other genres for this, and it's probably the best part of the Shock games - because every single room you enter seems to have a story and past history of its own.
Get that into a free roaming world, even in a limited way, and you'll get one happy gamer in return.
That's how you do non-linear worlds correctly, and exploration can never feel quite right in linear games, because you know you're supposed to be there - and you know it's all part of som rigid developer vision hand-made for everyone playing.