The Curious Expedition is one game that's trying to make this work - traversal of terrain as an important part of the gameplay - and I'm very excited about it. Yet it abstracts away the terrain itself into a manageable hex grid.
In fact, there is only one game I can think of which really manages to have an organic concept of "rugged terrain" and "hidden": Minecraft, with its huge detailed worlds. Simply put, it takes me more time to traverse a dense forest than some plains, because the latter is easier to navigate. The challenge of the terrain isn't distilled down to some "move cost" number but arises from the action of actually traversing it. Equally, in Minecraft you can really hide something. Put an entrance into a random forest valley, and it will take a long time to find without a map.
These properties make for a great game about expeditions and adventure, but they are somewhat undercut by Minecraft's other features. Because the primary focus of the game is on mining and crafting, a lot of the rugged terrain can by ignored if you're willing to spam blocks or make random tunnels. This also means that you can hide places simply by putting them underground with no visible entrance, and equally, you can get into places by mining, bypassing any clever traps or hidden door mechanisms. Nor is Minecraft's environment very harsh: there are monsters, of course, but you have near-unlimited carrying capacity, you heal rapidly, and you'd be hard pressed to actually starve.
What comes out of this is a potential mutant version of Minecraft that would be all about taking long journeys, navigating the landscape (with no convenient coordinate indicators or detailed magic maps), surviving the environment, finding hidden places, evading the traps, and getting the treasure. Raiding tombs, you might say, but in a world as big as the real one.
This game could be implemented as a Minecraft mod, of course, but it might be more interesting to make it its own game - mostly to pick a smaller block size. Minecraft's block size has led to somewhat awkward compromises in that the player will automatically ascend a half-block but not a full block - except for the pocket edition, when full block height changes can be automatically traversed too. In a game that's very much about the properties of terrain, it would be nice to have a bit more fine control over this, with blocks that are maybe a foot across. Single-block climbs would be dealt with automatically, though with a bit of a slowdown as a result, while larger height differences have to be jumped or climbed. Making the block size so small that the player can't fit through a one-block gap would also allow for things like thickets that have only the occasional path through.
Of course, a smaller block size means higher memory requirements for the world, but on the other hand, this game features no serious terrain modification: you cannot mine through rock, so a lot of the world can simply remain inaccessible and empty.
Anyway, I'm not sure if this would end up being fun or simply tedious. It might be an interesting thing to code up at some point, though writing a whole fat voxel engine is a bit much for a quick prototype. We'll see.