Definitely make enemies more difficult to kill. Give them more health, increase their attack damage, more puzzle based enemies, enemies with unavoidable attacks. Oh, and, that thing Skyward Sword did. You know, improved enemy AI.
Also, I would put more difficult puzzles not only in the dungeons, but outside as well. Maybe make a puzzle the key into more dungeons. Maybe make more puzzles as boss keys. Recent games have been slightly lacking in the puzzle aspect, so future games should really improve upon it.
Also, make the games less linear. Zelda is not a platformer, so the incredible linearity that was put in the most recent games lowered the difficulty by a ton. Not only are the dungeons too linear, but the games force players to take one specific path to complete the game. Older titles did not do this. What I mean is that dungeons in some of the old games could be completed in an order not intended by the developers. Recent Zelda games are very limited on this aspect, and it makes the games that much easier.