I think mine was Ultimecia. I had Lionheart and everything, but she'd always manage to (I can't remember the spell name) knock my HP down to 1 and then Apocalypse me. Not to mention how many times I had to soft reset and start all over because she blew away the magic I had junctioned to my HP! She was pretty hard. Plus, in that game, the bosses and monsters leveled up as you leveled up, so....
This one wasn't an FF, but it was still Square. Deus from Xenogears. Since you had to fight him in the gears, your level didn't really matter. There were only so many upgrades available to you for the gears. :(