My favorite part of those games is the Arcade-like simplicity in gameplay. Simplicity matched with difficulty makes for a game that no matter how many times I die, I will always try again. Great roguelikes and arcade games do this. They either make it so you don't feel that frustrated when you die and you just want to try again. Or they make it just frustrating enough so that you want to show that *Can'tSayThisOnTV*ing game who is boss.
I also like when there are points in which I am extremely overpowered, but a few seconds later I'm running for my life. It's a surefire sign of great level design. Reward good players with being overpowered for a bit, then throw them right back into the difficulty. I think the term for this is pacing. I love well-paced levels. A great example is Super Metroid. You struggle for a bit to get a power up, then once you get the power up, you get the chance to use it a lot, and you feel really awesome and cool. Then, you are given some challenging situations in which you have to use that power up.
Cave Story does this a lot, and I love it.
OH, and replayability. If I can come back to a game even after I beat it and still enjoy it, I'm in love. What helps this is generally randomness (e.g. in Roguelikes/Binding of Isaac), freedom of choices (Cave Story, Elder Scrolls) and/or simplicity (Arcade Games).
Summary: Simplicity, Good Pacing, and Replayability.
Hope that helps.