You still have to figure your way through and explore the dungeons regardless if the puzzles or obstacles mostly ends with finding a key. It's still absolutely discovery; then again some people try to tell me with a straight face that Skyward Sword has no exploration, and we're quoting Egoraptor now to boot.
I'm old enough to remember playing The Legend of Zelda with my older brothers. I remember staring at screenshots and looking at the artwork and the map and wondering what was out there. It really felt like anything was possible.
In the 3D era, it never once felt like anything was possible. It felt like I was at a theme park, as a celebrated guest, and the game was guiding me through it. It felt like a tour of what it
might look like to explore and discover things, but I'm not
really doing it. The game designers were on my shoulder the whole time.
I know this is partly a me thing, and I just like my exploration-focused games to feel indifferent to me. I think that's what makes them seem alive and important -- That they feel like they'd go on existing even if I wasn't there. Dark Souls in 2011 is what turned me back on to video games. It was the first game that recaptured that childhood feeling of anything being possible.
I'm super excited for BOTW because it really looks like they've learned from their many mistakes.