These are the bosses I thought was hard the first two times I played FFVII:

1.) Carry Armor: Yeah, I'm surprised no one mentioned him/her/it in the beginning.
2.) Materia Keeper
3.)Demon's Gate (yeah, he was hard)

and jenova synthesis, bizarro sephy, and safer sephy. You got to admit, the very first time you try to beat them, it was hard. But now!? pffft....