Another Sky temple/palace would be awesome, not like City in the Sky, but more like the palace of winds in MC. 3D Zelda should have more sky dungeons after all.
And in my opinion, 3D Zelda also needs more Dessert dungeons, and they should be more like Spirit Temple, not like Arbiter's ground. Another temple like the temple of time in TP would also be awesome, and the "electric temple" idea that was suggested earlier sounds great. That could be combined with the style of the Temple of time.
Shadow temple suggestions sounds great too, but what I would really like, is a combination of the Earth temple and the Shadow temple. So you REALLY get the feeling that you're deep down in the shadows.