A lot of bosses have given me trouble, especially optional ones, and so I can't really think of any one that stands out as the hardest. For story bosses it's a bit easier; I'd have to say Final Fantasy VIII's Ultimecia and, to a lesser extent, Final Fantasy V's Exdeath. Exdeath probably isn't as tough as I remember him to be, but Ultimecia is the only story boss from a Final Fantasy game that I haven't beaten without abusing in-game mechanics (in her case, card modding Bahamut into 99 Megalixirs, casting Aura on Squall and spamming Renzokuken + Megalixir every turn).

Legendary bosses - and what makes them legends:

Jon Irenecus - Most Difficult End Boss
Firekrag - Best Dragon Fight
The 100 Kratos clones at the God of War - Creative, tough, a incredibly cannon to the story.
Orrenstein and Smough - If you don't know, you don't WANT to know
Dark Samus on metroid Prime 2, on hard - This is probably one of the only games I know of who introduces a whole new end game boss on hard mode.
Dark Link on LOZ 2:Link's Adventure - My proof that I am video game legend. Yeah. I've beat him. No. I did NOT use the cheap way. I did it for REAL.

You don't need megalixers for Ultimecia, just http://finalfantasy.wikia.com/wiki/Renzokuken#Lion_Heart and http://finalfantasy.wikia.com/wiki/Combine_(Final_Fantasy_VIII)#Combine_Skills. It only seems like abusing the mechanics, since junctioning properly makes the game too easy.