I thought the fire temple boss in Ocarina of Time was absolutely frustrating. I can handle the rocks and some of the fire, it's just that it keeps rubbing against me, taking out my health through contact damage.
Supposedly Jafar in Kingdom Hearts is easy and Genie Jafar is challenging, but it was the other way around for me. Jafar was harder for me and Genie Jafar was rather easy. Also, Malificant(sp?) was pretty hard for me, but her dragon form I beat on my second try, and not with the glide on her back trick. Hell, I thought a lot of the bosses in Kingdom Hearts were very hard. Probably because it's one party member and a couple of random guys who occasionally heal you or hit someone.
Not exactly easy, but Giga Gaia from Chrono Trigger doesn't get enough hate for his dark magic combo at the very start and his two hands.
The rolling boss in Metroid Prime you have to beat to get the spider ball took a good deal more repetitions than Omega Pirate for me (Omega Pirate was challenging, but not quite as hard as everyone says he is). Also, beam troopers are just terrible, especially when there are multiple of different kinds.