Contra: Hard Corps on SNES. The game will make you its master for the first while, but once you get used to run and gun, and you refuse to stop for anything, the learning curve sort of takes a nose dive.
Double Dragon II: A lot of people will disagree because this game can still whip your ass if you don't play it smart all the time, but once you master the jumping spin kick and can do it over and over and over again, the game is miraculously easier.
Tony Hawk Series: Maybe not being a skateboarder myself, I found this game brutally difficult to learn, but once you get a good flow going and master the manual (the move, not the instruction manual) you can string together million point combos no problemo.
Dragon Warrior NES: The first RPG I ever played, and boy did it take me a long time to figure out not to stray too far away on the world map. You can fight 90 blobs with you have some medical herbs, but run into one warlock or gold golem and you have zero chance of survival. Realizing that you have to take it slow, always have plenty of herbs, and don't be afraid to run to town if you're almost dead. The first game where patience and levelling up was the key to success.
Shadowgate/Deja Vu NES: Point and click mystery games. Impossible (it seems) to figure out, but figure it all out once, and you know it for life.
Punch-Out: With the exception of Mr. Dream/Mike Tyson who is damn near impossible every time you fight him, if you figure out the strategy for each individual boxer, the game becomes a cakewalk.
If I think of some more, I'll edit this post.