KDR, I agree. More strategic and harder battles, is a must, if Zelda is going to get any harder. Battles should be "mini-dungeons" in a way. You should have to figure out what item is best to be used, as well as the proper time to attack, dodge, block and such. AI should be more adapting and more random though, making them harder and more fierce. They all around shouldn't be so predictable. When I'm faced with 4 or more enemies, I want to feel like death is definitely possible.
With harder battles, comes tatics upgrades, and items to help the player along. They could have a move upgrade, such as a special parrying, and a magic upgrade akin to Naru's (sp) flame. Plus, these items or upgrades can be recieved through trade quests and such, making more side-quests/mini-games more than just a rupee GET.
Not to mention, it would slow down the coasting through dungeons, giving you a sense that dungeons are more than a brain tease. Instead of easily going from puzzle to puzzle, you would go from puzzle, to fierce battle, to fierce battle, to puzzle. While not making the dungeon longer, it will feel longer.