The Water Temple was somewhat hard the first time around, but it became so much easier when played over.
I couldn't decide on just one, so here's my small list of the dungeons I find the hardest.
Eagle's Tower (Link's Awakening)- So. Many. Floors.
Great Bay Temple (Majora's Mask)- The switch-pressing was tedious, and many of the rooms looked the same. Those Dexihands didn't help much either. I HATED having to use currents to move inbetween each room.
Stone Tower Temple (Majora's Mask)- I actually got nauseous when the tower flipped upside down... probably why it was so hard to beat
Snowpeak Ruins (Twilight Princess)- It would have been a walk in the park had there been no block puzzles... I'm terrible at those.
Sky Keep (Skyward Sword)- Again, I have the worst time with block puzzles, so this one took me a while...