Oh man Abuse was totally hardcore. I can't recommend that one highly enough--it was basically THE first side scroller to use keyboard move + mouse aiming. Also it was awesome in multiplayer, because you could pick up the stealth kit, hide against a foliage background, and then shank somebody with a lightsaber when they ran by. And oh-so-moddable. I don't know why this one didn't really take off.
A few people are recommending shmups. I grew up on Tyrian which was awesome, but I also liked
Raptor: Call of the Shadows (it was shorter, but more filling, than Tyrian). If you want something arcadey,
Giga Wing is a classic one if you emulate it. Oh my god the scores get so high, you would think you were playing pinball.
Commander Keen 4.
Jazz Jackrabbit which was like a cross between Duke Nukem and Sonic the Hedgehog, if more than a little dorky.
Prince of Persia and Out of This World.
Oh yeah.
TURRICAN, kind of like Contra and every gamer should learn to recognize that music. It was on every single console of that era, too. And
GUNSTAR HEROES. It had a pretty innovative weapon combination system.
...If you haven't played Super Metroid then this needs to be remedied posthaste.
Edit: OH OH
BLASTER MASTER. Well, it IS a classic. But then again so was "A Boy and His Blob" (which I'm not going to link).