Well there was a game called Frogger, but the original gameplay was only a small part of it. Did it have a way to play the original game? I can’t remember
Contra, Rygar, Ninja Gaiden I and II, Mike Tyson’s Punch-Out, Bionic Commando, and Dragon Warrior III come to mind as being tough. I’ve never beat Mega Man without the Elec Man pause trick so that probably doesn’t count