I think this sense of discovery is one of the reasons I love Minecraft so much. Wandering in a deep cave, trying to follow the sounds to find a stronghold or spawner is amazing. Mining a wall and suddenly finding some diamonds is so rewarding!
Discovery creates an amazing gaming experience, but it takes some patience to get it. It might be frustrating at the beginning. Back in the early 90's you just had a few games, you had to get most of them. Now, people are exposed to millions of games for several platforms. If a game doesn't catch the attention of a player in the first few minutes, it's ditched for another one.
It's the market what's sinking Zelda, sadly...