Now that we're talking shooters, I think Gradius III is pretty hard too. I've got the cart, but the only way I can beat it is by using the save/load state method on an emulator Yams mentioned. I saw my aunt beat it from start to finish once (the same aunt that used to whoop my butt in MK II, and the same one that showed me how to play A Link to the Past), and I was in awe.

Gradius IV is probably harder, but the unlimited continues balances out the difficulty.

Gradius V is somewhere in the middle.