Someone mentioned the Biolizard from Sonic Adventure 2. The first time I fought that beast, I beat him without a problem. Everytime after that, he stomps poor shadow. I think it's because the game is a little glitchy, but I never use that as an excuse.
I think the hardest boss is the last guy on Teleroboxer for the Virtual Boy. Man, it was a hard fight getting there, and he was relentless.