I played a lot of Ocarina of Time 3D within the last couple of weeks, remembering Ocarina of Time (even though the original game was only fifteen feet away from where I was playing it, still in my N64 (I also played it a bunch before I got OoT3D for Christmas). While the Water Temple is hard, it's only hard if you don't inspect every nook and cranny and be sure to collect every key. As the others above me have said, I believe that the hardest temple is not the Water Temple, but rather the Shadow Temple.
Before you get the map, even when you have the Lens of Truth, it's a very, um, unearthly-designed dungeon. There are many doors and passages that you would never expect to see, and the only way to get the Lens of Truth to work as long as you'd want to would be using the Song of Storms glitch. There are some vague hints throughout the dungeon, like its sister dungeon, the Bottom of the Well, and I applaud that they make the player think, but it ends up happening quite a bit.
There were some clever things, though, such as bombing a pile of bones in order to find a chest that holds a key, or tossing yourself in to the wind. The most devious puzzle I could think of, though, was when you had to shoot a fire arrow at the bombs in order to destroy the statue, forming a bridge.