Recurring characters? I'd have to go with Ganondorf, like so many others. Not creative, I know, but he's one of the coolest, most evil villains of all time. I hope he's in Skyward Sword, though judging what's been said about it so far timeline-wise, I doubt it.
As for characters who aren't main characters, Talon comes to mind. Being a lazy farmer is not only funny but also fun to watch as well.
Another favorite would have to be Syrup the Witch. One of the most frequently recurrring but also most forgettable characters in the series needs some love too! Her potions are always helpful, and her theme music rocks.
Other notables are Tingle, the Lakeside Laboratory professor, Pierre the Scarecrow, Biggoron, and the Postman.