God of War, CastleVania LOI & Rygar...
I only played DMC 1 and 3 (I heard 2 was abysmal), and I played DMC1 way back when I wasn't really "into" games (meaning I didn't pay attention to game design) as I do now, but I did play DMC to almost the very end - I couldn't beat it back then (I also sucked at games back then).
DMC 3 is great. DMC 3 is hard, which is one of the reasons it's great. It's got a lot of overabundant style (the director of the cutscenes also directed "Versus") and it's fun. The fluidity of which you switch in between melee and projectile weapons with L2/R2 is quite nice, once you get used to switching on the fly. The enemies are tough, but after a while they become not so tough as the enemies in Ninja Gaiden. Also, the PLII sound system is nice, and the major cutscenes are in DD. A good game. But if you're feeling iffy, I'd seriously suggest renting it. This game can be quite tough, especially in the beginning when you don't know what you're doing. They sell it used for something like 5-10 dollars less, so I wouldn't recommend that route....
Ninja Gaiden is the reason I now like hard games. It's the reason why I play God of War on Spartan and refuse to take it down a notch if I die too much. It's one of the most rewarding gameplay experiences I've ever had, personally. There's a tangible immediacy to the battles. The enemy AI is tough; it's almost like a one-on-one 3D fighter like Soul Caliber, except you're fighting against five guys instead of one. The character progression is also nice and keeps things tough but interesting: upgrading your sword gives you access to new techniques and moves, but they're only useful if you can pull of the button combos. I don't know how many times I died before I got past the first level; I don't know how many times I died trying to get past the big dude with the nunchucks. Prepare to die. A lot. But when you finally get it, you get it. After I beat the first level, the subsequent levels came a lot "easier" in the sense that I knew what I was doing. Get a copy, die a few dozen times, enjoy every minute of it.
Alas, I still own a copy of Shinobi (not Night Shade), but I can't bring myself to like it. The combat system, while interesting, is pulled off in a greatly dull manner. When you defeat an opponent, they freeze in their death throws. You try to kill as many opponents as you can within a set time so that you can accumulate points for style. But, sloppy controls, poor graphics, and boring level design really kill it for me. Because of this, I haven't tried nightshade...
If you like the original NES gaiden, play it 🙂 The cartridges aren't that hard to find. I would stay away from the SNES trilogy "update." It's quite rare (thus expensive) and many consider it to be disappointing. If you all ready have the games on the NES, play them on your PSP via emulator...🙂