Legend of Grimrock is pretty damn hard - but it is good to play a solo RPG that poses a challenge for a change - instead of grinding for over-powered weapons, you have to really stop and think, and plan how to deal with the puzzles and enemies. It's kinda retro, like the 16-bit dungeon crawlers like Bloodwych, Eye of the Beholder, or Dungeon Master especially.
There's also Minecraft Tekkit - a different kind of challenge, that's really more about engineering than anything, even survival - but it can be a lot of fun to come up with an idea and develop it with Tekkit, trying to keep everything neat, trying to avoid explosions etc etc. I think playing hardcore mode Tekkit is about as challenging as any 1 game should ever need to be.
For the DS, well Scribblenaughts is awesome, sometimes you have to really think about how to solve the levels, sometimes you solve em with pure luck, or by methods that other games just wouldn't allow. Room full of zombies and dinosaurs? - spawn Chuck Norris, job done.
N+ on the DS is worth a look as well, if you like challenging platformers like Meat Boy.
Torchlight can be pretty damn difficult as well - that's more like LoL I guess, maybe worth a look as it'll be dirt cheap - in fact it was part of the last Humble Bundle, which is pretty awesome if you consider how big Torchlight is.
And Binding of Isaac, it's basically the dungeon section from the original Zelda game with some awesome sick humour, lots of variety, every game is different, but most importantly it's a hellish challenge, I've still not managed to kill mom after 6 months or so of playing.