It is quite interesting that people think puzzles and battles have similar importance, so the best recipe for dungeons could be to make dungeons to be one half of puzzles and the other half consisting of battles, where battles and puzzles alternate. This is more or less what official Zelda games do, so this pull does not say something new...

In my opinion, a lot of variety of puzzles is needed. Apart from key-door puzzles (or weapon-obstacle puzzles, which are in essence the same), it is cool to find from time to time some intelligent and original puzzles. I don't mean complex or annoying puzzles like a sokoban-like puzzle with too many blocks or things like that (those are quite boring). I mean a bit of innovation, although this is quite hard to do and one needs to be very creative.
I agree with @the_bread that one of the coolest things is when battles and puzzles are mixed, but this is usually done only for dungeon bosses; so maybe adding more number and variety of bosses and minibosses could improve the game (althought that means more work for the art part). Also, it is not good to see that almost always the bosses have to be killed with the weapon of that level (there are some exceptions where you need an item from a previous level or an item that is bought at some shop), which maybe should be changed to give more challenge.
I also agree that the story is very important to keep the player focused on the game, but the exploration seems to be the most important characteristic for a Zelda-like game. IMHO, adding many many mysteries and secrets to the overworld maps is one of the important things that give quality to the exploration part (and they force the completist players to backtrack if they want to find all the secrets and easter eggs). Also, too big and empty maps are usually boring for the exploration, but secrets and mysteries contribute to fill them with more fun.
For those who are bored, this is a funny video comparing OoT and ALTTP, where some gameplay elements are analyzed:
https://www.youtube.com/watch?v=XOC3vixnj_0