Nethack was very easy to me. Just sayin'.
Anyway, I'm not sure what you call a "rogue-like" game, but the PMD series is amazing. They are in no way dumbed-down, and as you progress the later levels are hella hard. Really hard. It does have a storyline that makes it well-rounded, and the beginning levels are easy to overcome. Once you start progressing further, it get's hard. The characters not only have HP to worry about, but PP and a new "hunger" system that depletes with each action in a dungeon. Going in to a dungeon without food or items that restore PP makes it all the more harder. And when you beat the game... no, no spoilers here, you get access to special dungeons that restrict things like how many Pokémon you can take with you, how many items you can carry in your bag, temporary level resets to lower levels, etc.
I wouldn't call any Pokémon game "dumbed-down". It's a franchise for anyone.
EDIT: Looked up "rogue-like" video game, seems to fit your post. You would definitely love the PMD series if you like those kinds of games.