See, this is what I don't like hearing. People complain about new Zelda games being too easy, but then give up on the harder ones. It's not that hard a game if you handle it properly.
1. Take dungeons one level at a time. Go all the way left on the main floor, see where it takes you. Can't go any further? Head back to the right and see where it takes you. Think about when you go down an elevator where you end up, and how far down you go. Don't just run around everywhere. There isn't specific puzzle rooms -- the whole dungeon is the puzzle.
2. Handle levelling up properly before you run into a dungeon. Mess around in the forrests and gain XP before venturing into a dungeon. It's a lot of work, but try to balance out so you're roughly at the same level for each category.
3. Use magic wisely. Use Shield and Life often. If you have the chance to grab a magic bottle, especially a red one, use Life even if you only have one block down, then grab the bottle to refill. It's simple, and it works.
4. When in doubt go down and to the right. This works in dungeons and also Death Mountain. It's not a fool-proof method, but it often works.
But really, to answer the question - I found it challenging, but not difficult. I played through the whole title on the original NES, without save states that can be made with an emulator or the Wii VC. It took awhile, but it's doable without walkthroughs or cheating.