I remember now that I had a heck of time fighting Velius in Final Fantasy Tactics. The first Lucavi was pretty easy and wasn't meant to be too difficult, however, they must have expected you to be on some super high level when you got to Velius. He was a huge jump above anything else. Even the later bosses after him weren't anywhere near as much of a leap as he was.
Hardest boss? Mishaela from Shining Force. you fight through her minions, you get to the bottleneck leading up to here, you get her surrounded and start pounding on her... then she casts level 2 bolt and takes half the life from about 10 members of your party. Of course, you have plenty of others, but then she starts whacking people around for 1/4 health a pop. Funny thing is, she only has about 60 health. Man, what a bitch