Thinking way back to my first playthrough, a few bosses stick out in my mind:

Demon Wall for sure, that weird claw robot in the submarine dock, and Safer Sephiroth.

Oh, and also that part at the beginning where you have to time the button press with Tifa and Barret frustrated me, though now I'm not so sure why...