As my first souls game, the gargoyles at the rough top from dark souls had me in the fetal position, crying in the corner. It took me at least 3 days to take (playing about 2 hours each) to finally take them down. It was a rental so I didn't get far enough to encounter another super tough boss.
Sephiroth in Kingdom Hearts was also hard as shit. It took a lot of grinding and failing to finally topple that mother fucker.