Kefka, for an actual god, wasn't that tough. But in his defense it was 12v1.

Ultimecia wasn't that tough either, but as been said VIII is incredibly broken. In my playthough the difficulty took three different nosedives. First when I learned how White Wind works and dumped everything into Quistis' HP. Then when Quistis learned Mighty Guard. And finally it just plummeted when I could make my own Aura and Invincibility Potions.