Finally they prove these games are as hard as flipping pancakes!
Joking aside, being NP-Hard doesn't really correspond to difficulty. It was pointed out in another comment that since the levels are fixed, they cannot be NP-Hard. Another then said people have altered the levels on many of these games, but that still doesn't mean much. There is no set of levels that could prove it.
Being NP-Hard is a property of at least one of the mechanisms in the game. For the proof, the mechanism is shown be able to encode an NP-complete problem in such a way that if you could solve the game mechanism's problem quickly, it can be shown to quickly give solutions to the NP-complete problem. So it's not really any specific level, its the ability to embed other "hard" problems into the level and being able to translate the solution back quickly that's important. (IE, it's hard because it's solution can "automatically" solve other hard problems quickly)
Odds are if you saw the levels created by translating 3-Sat problems (or whatever they used for the reduction) into Mario levels, you'd think the levels were not fun in the slightest. Then again, it could be cool to let people input some 3-Sat problem and then go play the Mario level and see the answer they generated by beating the level. Anyone wanna make that? And then input the levels into Super Mario Crossover 2 so I can use the Blaster Master tank
Speaking of Blaster Master, I got a kick out of reading other people's experiences with those old NES games. It seems the harder those games were the more I liked them. Kid Icarus, Battletoads, Blaster Master, Fester's Quest, and Solomon's Key were mentioned, but also Teenage Mutant Ninja Turtles (the one with the swimming bomb-defusing second level), Friday the 13th (though once you know how Jason attacks it's too easy, even just throwing stones), the first Mega Man (without using the repeated select button trick), Bart vs. The Space Mutants, Double Dragon III, Ninja Gaiden Trilogy, Deadly Towers, Rush 'n Attack, Snake Rattle & Roll, Mike Tyson's Punch Out, Metroid, Gauntlet, Castlevania, Nightmare on Elm Street, Little Nemo, Legendary Wings, Bionic Commando, Guardian Legend, Zelda I & II, Marble Madness, Werewolf, Legacy of the Wizard. I've got nostalgia for each one (maybe because I spent enough time to memorize the levels, develop my strategy, and finally win), not to mention the various RPGs but those are generally less difficult. Thank goodness for emulators