Strangely enough, Skyview temple. I just found it....different. The music just fit perfectly and you have to admit that was one of the best 1st bosses in all of Zelda's history. I think it also has to do with the fact I've been watching so many people play it in the demo for months that to finally, FINALLY play that part it just felt 100x better.
I really can't decide between the Earth Temple and Sandship. Those two dungeons were unique and intense in both puzzle and combat. (They both have the dreaded "stun boss, slash weak point" style boss battles, though. At least Tentalus was a bit more diverse than Scaldera.)
Skyview was my favorite, it's extremely simple and a welcoming first dungeon. Of course, I'd rather have a tree as the first dungeon a la Ocarina of Time, but beggars can't be choosers. I also loved fighting the boss contained in the dungeon, it was just so...fabulous!
Ancient Cistern is my favorite because it had very unique puzzles and was a very lengthy dungeon. The final boss was amazing as well. And worth mentioning, Sandship comes in close 2nd because it's so unique.
Sky keep is my favorite, although the sandship is great, but the sky keep has so much more to it, there are more puzzles than just hitting a switch and shooting through a couple fans, it has everything in it and all the moving of the rooms makes you have to think of where you need to go next.
I haven't entered the Sky keep, so I didn't vote for it, but I heard it wasn't a linear dungeon.
Sandship was a there-and-back-again dungeon that had me stuck in places for minutes at a time unlike the other dungeons.
Along with the aquiring of the bow and arrow, this dungeon wasn't a simple and is my favorite.
Mine was the Ancient Cistern. I always loved water dungeons, so going through the first part of it, I already enjoyed it. When I figured I was getting near the end, I had basically just passed the half way point. That's when it turned into the underground, undead dungeon. So, it mixed some of my favorite things together. Water, darkness, death and decay! The whole dungeon was a nice size, and I just found it very enjoyable. Koloktos was great. I enjoyed the Sandship as well, but I didn't find it quite as creative as the Ancient Cistern (I love pirates though), so I enjoyed it especially for that reason.