There's so many games I couldn't know where to start. I am not particularly skilled with games.
Double Dragon series comes to mind. Arcade games I only beat by cheating using MAME and having virtually infinite money coins, I have to use probably some 60 coins to beat the games ! The NES games are all so hard I can only beat them using save states. Super Double Dragon is easier, but I still end up dying always at the same place I don't remember where exactly but it should be in level 4 or 5. It's also less good then its predecessors.
Then there is the Castlevania series. Actually I didn't beat that many legitimately, I beat Castlevania II, SOTN, the 3 GBA games and the 2 first DS games... and that's it. I never managed to beat the original Castlevania nor Castlevania III legitimately and I always get stuck at the same point, death's stage, in BOTH of those. I of course finished them using save states or easy mode hacks many times, but no matter how much I play them I can never beat death. Super Castlevania IV I got to Dracula legitimately but never beat him without save states. Dracula X... don't even get me started. I am currently stuck in Order of Ecclesia, the boss is so hard I don't think I'll ever manage to beat him.
I cannot conclude without mentionning NES Battletoads. Very great game, I beat the underground tunnel legitimately a lot of time, I think it's difficulty is overrated a lot on the net. However I cannot manage to beat the Rat Race legitimately.
The only game I can beat (legit) is Life Force (Salamander)
Wow, respect !! I beat Life Force many times with the 30 lives code, but I couldn't possibly imagine going further than the 2nd level without it.
And I agree about gradius games being hard but awesome.
Even I managed to beat the NES Contra without the 30 lives code, and I am not particularly good with action games. Super C on the other hand.... is much harder (and for the most part, much better).