In the US FF II I beat him in my first try.
In teh GBA version he kicked my behind 5 times before I finally could beat him. He used Big Bang every turn and healing was a pain...
Now with all Ultimate Weapons, I screw him, and with soem mega-elixers he has become quite easy, but I still need to watch out, for hsi Big Bang still takes away 2000 HP with everyone.

So yeah, he is one of the thougher cookies in FF. But Neo-X-Death was harder, IMO.