King Calamari in Mario RPG. He's not hard, but always manages to make the fight much more annoying than it needs to be by throwing a party member in the air, taking them out of the fight for 1 or 2 turns, and when they get back, it's inflicting the "fear" status ailment which lowers their attack, thus making the fight drag on a lot longer than it should.
Kessler while playing the Hero on InFamous. It's not that he's hard, it's that he has WAY to much HP, and this fight is x1000 times faster with Arc Lightning.
2nd stage Lavos from Chrono Trigger (on first playthrough). You can fight Lavos at almost any point in the game. There's even a way to bypass the first stage. But you need to be at a certain level to even survive the first few SECONDS of the 2nd stage. No matter what level you are, he starts right off the bat with his most powerful attack (simply because if you act quickly, he'll never have a chance to do it a second time.)
The big moth in the Dark Forest in Zelda: Link to the Past. Once again, not hard, but VERY annoying. You are on a moving floor, with spikes that move around, fighting an enemy who can move effortlessly over said spikes and floor. Hell, there are plenty of bosses from this game I could classify as annoying, this one was the first that came to my mind.
Henry from No More Heroes. An awesome fight, but DAMN, that motherf***er was hard! The fact that he had a One-Hit-Kill move didn't help, either. Need I say more?