Contra: Hard Corps. Just how hardcore are you, boy? The japanese sissies needed three "hit points" per life. You play it like a man who plays CONTRA goddammit, one shot and yer dead as shit. Probably the hardest Contra game as long as you can block out those pretty bad parts of Contra 3 where you played from an isometric point of view. Multiple character choices each with different weapons, multiple branching paths, a storyline and multiple endings makes this my favorite Contra, personally.
Splatterhouse 2. Not that much depth, but I have to suggest it for being one of the first really good horror-typed videogames. Also, one of the most underrated series of games ever, and number 2 happens to be the best one. So don the hockey mask, grab a 2 by 4 and smack some zombies messily into the walls, damnit! The game's pretty difficult, but not stunningly so.
Streets of Rage 2. I say 2 because 3 had the stupid robo-geezer and the kangaroo. Streets of Rage 2 is a classic beat-em-up that's plain simple-minded fun, and that just happens to have a bit more depth than several beat-em-ups ever could (the only deeper one I can think of for a home console? Turtles in Time).