I think the reason old games were inherently harder is because of a few reasons...
1) You were a lot younger and a lot less technically skilled
2) The Nintendo D-Pad was a cruel, cruel mistress, especially with 8-way controls.
3) Older games (generally) had a more poorly written hit detection compared to stuff we have today.
4) Older games WERE just plain harder because beating them was the accomplishment, there generally was no easy mode, and there were no achievements. Beating the game was the achievement, and if it had a battery your high score proved it. Beating the game on a self imposed time trial or 1/no hit challenge was a personal accomplishment.
Having said that, I'd say that finally getting to Wiley's castle in Mega Man 2, with no cheat codes, was probably the closest I came to beating a Mega Man game, and that made me proud.
Difficulty aside, I get a sense of accomplishment whenever I beat an RPG game that has more than 30 hours of playtime in it. (I.E. Skyrim, Fallout games, Mass Effect, etc)