Currently Online 
A lot of games in the NES/SNES days weren't actually that hard. They just required you to learn timing. It was memorization based rather than being dynamic. Mike Tyson's Punch Out, which the OP cited as being hard, was a game that I beat pretty much every day without losing after I got the timing down. It was pure cake after that and quite short. I would come home from school, beat a few games that I owned, like Punch Out and Double Dragon II, and then I'd go do something else. As others have said, I think they were trying to mask a relatively small amount of content.
I've always thought the twitch gaming of the arcade/Atari era was harder, as those games often pushed you as far as you could go until it became impossible to keep up.
Personally, I prefer dynamic gaming to memorization based gaming, even if the end result is that it takes less time to beat an encounter.
