Let's not rule out difficulty levels though! Sometimes a simple answer can be a good one. In my personal opinion, the optimum difficulty is a variable difficulty. I don't know anything about programming, but I can't imagine it would be THAT astoundingly complicated to implement a simple difficulty system like this one:
Normal: Enemies/Traps do 1x Damage, Enemies have 1x health
Difficult: Enemies/Traps do 2x Damage, Enemies have 2x health
Die in a Fire: Enemies/Traps do 5x Damage, Enemies have 5x health
That would allow people to have the option to, well, die in a fire... if that's how they want their Zelda experience to be.
In addition, enemies should get progressively more difficult throughout the game. I think that if the player has access to fairies and 15+ heart containers by a certain point in the game, it's fair game for enemies to do several hearts of damage per hit.
As others in this thread have pointed out, there are more factors to difficulty than just enemy strength. As for puzzle difficulty, it's really hard to quantify how difficult it is. Some puzzles are instantly obvious, while others take a long time - and which puzzles are difficult vary from person to person. I would say that the current puzzle difficulty is probably about right for the population that buys and plays Legend of Zelda games. Would I personally like more difficulty? Sure.
I think given the ubiquity of internet walkthroughs, it wouldn't hurt to have more difficult puzzles. The people who want to challenge themselves by avoiding walkthroughs could still do so, while those who are having a harder time and don't want to spend forever solving one puzzle can look up answers or consult an in-game resource for hints. But again, difficulty of a puzzle is mostly subjective, so it's hard to say what is really a proper difficulty. I'll leave that issue to those who are more equipped to address it.
Another change that should be made would be to steer away from the Fi model of guide/player interaction. There is a 94% chance that Fi's repetition of the dialogue content immediately after it has been told to the player is asinine. The text of the game should make it reasonably clear (or even a little vague!) what you have to do, but with an option to "talk to [insert guide/fairy name]" if you forgot, missed it the first time, or are generally clueless.