Hands down the hardest game I've ever played is "I wanna be the guy". You can download it for free (!) here:
http://kayin.pyoko.org/iwbtg/
I estimate you will die >5 times before managing to leave the first screen. The bosses in that are insane.
As for disproportionate boss, there was a game I played as a kid called lego racers, and the final character was rocket ronnie. He was a cheating little brat. He raced on his own track, in a car that was designed for that track, and faster than anything you had available (you win his car if you beat him, but then what's the point?). He was so fast that the only way to win was to cheat and take a shortcut, which he took, but only when you weren't nearby to watch what he was doing.
I may have just found it hard cos of being a kid, but man, I spent ages on that stupid guy.