A good hard game is one that gives you the mechanics to dominate it and then throws a real challenge at you. Often changing things up on different difficulty settings. The Ninja Gaiden school of games (DmC, MGR:R, Bayonetta) fall into this category.
Then there are platformers that require precision timing. Often those are an exercise ion repetition. I will never beat the bonus level in Rayman origins, and probably will never get past that level (one of the later ones, circular) in N+ I got stuck on. But here too, the real criteria is how technical the game is. If the controls blow then it might be difficult, but for all the wrong reasons.
*.souls falls more into the latter category. Learn the level. And for the most part just don't rush into it. With the covenant of champions, DS2 does try to set foot in the first category, heck if you want you can try and SL1 a souls game with just a dagger, but I dunno, I love the games but I just wouldn't put them in the same category as a MNM or revengeance run.