The way I'm going to do it is first time playthrough and after multiple playthroughs
For first time playthroughs I'm going to go with The great bay temple ( with fairies ). The first big problem is simply the size of the dungeon. There are about 18 rooms in this dungeon which, by the way, is a lot of rooms. Being able to access only a couple of the rooms at any given time can get confusing when you are trying to figure out where to get to next. The next problem is the fairies. Most of them are pretty easy to get however, I can think of a few of them that could make even the best of zelda players go crazy trying to find them. Gyorg (The Boss) isn't too much of a challenge to me. It seems a lot of people have lots of troubles with Gyorg though so I thought it be good to mention him. Finally the most difficult part of the dungeon is a hookshot target. Who would think to just look up for no reason? That got me stumped for hours. Fortunately, this hookshot target is not something you'll forget which makes future playthroughs a lot easier.
Another one I'd like to mention for first time playthroughs is the Stone Tower Temple. It has even more rooms than the Great Bay Temple but, you have to double that for when you flip out|tou pilf the dungeon! The fairies are also a problem. Even more so than the GBT's fairies! I'll just leave it at that for the STT. Great music and atmosphere too!
Now for multiple playthroughs the hardest dungeon would have to be the Great Palace from Zelda II The Adventure of Link. This one is also a contender for the hardest first time playthrough but I didn't find it too bad. It still requires a lot of skill and beating Shadow Link was definitely a feat! It was confusing and easy to get lost in and all the new enemies it presented were no help at all in making it easier. I really enjoyed this dungeon though, despite the difficulty. However I hate Fokkas! Those fire shooting birdlike enemies!. At least the developers let you start at the beginning of the dungeon if you lost all your lives!