FTL, because you never know how things will work out. Each time you attempt it turns out meaningfully differently, and its unpredictability makes it challenging and addicting. Even on Easy, this game kicks my ass.
VVVVVV is another one that I had a hard time with. This game has its fair share of challenge (I died over 1100 times on my first playthrough, when I didn't really know what I was doing), but is remarkably forgiving, with very frequent respawn points (generally at least one on each screen) and a very quick turnover time between dying and respawning. It also has some great pumping chiptune to keep you going through the harder parts, and is the right difficulty to be just on the right side of being frustrating, for me anyway.
Braid, as well. It's quite easy to just get through the game, but if you want to get all the collectible puzzle pieces that you need to unlock the real ending you'll need to try harder and solve some ingenious time-based puzzles. And then, if that isn't enough, you can restart and try to go for the eight secret stars, which are in fact so secret that I didn't even know about them until well after I'd completed the game. (Seriously, there's nothing in the game to indicate that these exist. Not even a Steam Achievement for getting all of them.) You need to do some really cryptic sh!t to get these, including getting one before completing the World 3 puzzle, and letting one of the levels sit for two hours until a slow-moving cloud is in the right place to get it.