Best challenging-but-fun arcade game: Renegade
Shinobi and Rastan are both games that start changing the rules towards the end. I'd love to play through them, but they don't allow continues during the final, hardest stages.
Ghouls and Ghosts is challenging-but-fun, but when you get to the end the rules get really wonky, which makes the game fun-but-frustrating. The game always makes me start over at the beginning because I didn't do something right the first time around. Then I am fuzzy on whether or not I will make the same mistake again the second time around.
I think that Defender and Stargate are really freaking hard. Robotron is freaking-awesome-but-hard.
None of these games qualify as "hardest games", though. The really hard games I have played are not Arcade games. Shadow of the Beast II is probably the hardest game I have ever really played, and back in the day it was a good enough game that I tried to stick it out. Once I got to the final end boss and lost, but the whole process was so exhausting that I put the controller down and never put in the effort it took to make it that far again.
The Japanese Super Mario Brothers 2 is perhaps significantly tougher, I have not gotten far at all in the game despite repeated attempts. Here is a description from Wikipedia:
"Nintendo of America disliked the Japanese Super Mario Bros. 2, which they found to be frustratingly difficult and otherwise little more than a modification of Super Mario Bros.. As they did not want to risk the franchise's popularity, they canceled its stateside release and eventually decided on reworking Yume Kōjō: Doki Doki Panic into the Western Super Mario Bros. 2."