My very first time through I had some major problems on Bizarro Sephiroth. My party was so weak that he healed more than I was dealing him with his Bizarro Energy.
Then I went back out, did the (rather long) chocobo breeding quest to get KoTR materia. And when I first summoned it, it was pure bliss... those Kalm Fangs didn't know what hit 'em. :P
Bizzy died in one KoTR, and Safer died pretty quickly too.

Hmm, I'd say now they're too easy, but at the time they was more than challenging.