Sin from FFX caused me much hardship.
I remember Dark Samus in MP2 being painful too because of the time limit.

I think the hardest boss i've faced is the last boss in sonic 2, when playing as knuckles. The optional boss battles in ffX are hard I think but I haven't put much effort into trying to beat them.

Yeah, I can confirm that, I killed him as thief a while ago doing that.

As for OT, I'm not sure. There's never been a boss I've been unable to beat. I've gotten bored with games and stopped before doing everything, but I've never found any boss all that hard. They mostly all have some sort of trick to defeating them, and it usually doesn't take too too long to figure it out.

Maybe I'll remember something I had trouble with later, but nothing comes to mind yet.

343 guilty spark in Halo 3 ^^

Quake 4 on general difficulty (xbox 360), you have all those stroggs running around you while you're trying to aim up, and one hit kills you ( ok 2 hits ) it pissed me off to the point where i just gave up for about 3 months and then went back and finally accomplished it after 10 straight hours of non-stop trying. i thought my system was going to RROD, and it did 3 months later

Bob the Killer Goldfish from Earthworm Jim.

I still get nightmares...

Mildred of Arcana Heart 1.

Probably one of the Touhou bosses on max difficulty.

All the bosses of Megaman X6 on hard. Enouh said. Or Omega from Megaman ZX on hard.

True.  But without a guide it takes several times of replaying the entire tutorial level to figure that out.  For that matter, the Flamelurker on New Game + is ridiculous if you don't use the hiding behind the ribcage maneuver.

THIS!