Malicious (PSN) - Challenging, fast-paced and exciting beat-em-up with a surreal aesthetic and great music.
Unfortunately, it's only available in Japanese on the Japanese PSN. That doesn't have to be a barrier, though. The game isn't exactly wordy, and you can either experiment your way to the controls or check online. Incredibly, it only costs 800 yen (about $10).
Valkyria Chronicles - SRPG with shooter elements. Awesome if you like tactical gameplay.
Demon's Souls - Look, this is definitely one of those games you should play. I was put off it for so long because all people would talk about was the difficulty. Don't let that hinder you, it's one of the best action RPGs I have ever played.
Folklore - Action-adventure with RPG elements. A little iffy, still worth it.
Wipeout HD/Fury (PSN) - High-speed, anti-gravity racing. I don't play racing games, but I always make an exception for this series on account of them being so damn fun.
Wizardry: Labyrinth of Lost Souls (PSN) - Oldschool dungeon crawler. Emphasis on oldschool. That said, it isn't as punishing as you'd expect. I went into it completely unfamiliar with the genre/style and had loads of fun anyway. Completing the game took me about 30 hours, but I skipped some of the sidequests. A good value, considering the low price.
Disgaea 3 - I'll admit it: I haven't played this game. If it's anything like the first two, however, it should be a lot of fun (and last until the heat death of the universe).