The first super boss I ever beat in a game was Culex from Super Mario RPG. Took freaking forever.
Ruby and Emerald Weapon from FFVII were a bitch when I was younger. Though, I remember when the game was still new, my cousin and I were playing. We had no idea that Emerald's Aire Tam attack dealt 1111 damage for every piece of materia equipped. On dumb luck, we had two HP plus materia on Cid and Cloud, bumping their HP to 9999 each. Emerald used the attack right after a megalixer was used, and bam, both Cloud and Cid got lucky 7's. We nearly shat ourselves.
I also remember being completely outclassed by Sephiroth in Kingdom Hearts... though that battle seems super easy now.