You need to get a copy of Castlevania: Dracula X Chronicle. The game is easily one of the best values on the PSP, and a fine title as well. It is a 3D remake of a game that was never properly released in the West. The game is a transition title between the original style of Castlevania, and the more open-level Symphony of the Night. And as an added bonus, both the original Rondo of Blood and Symphony of the Night can be unlocked in the game. That's easily 60+ hours of gaming in one PSP disc. And the game can usually be found at most used game stores for less than $20.
On the RPG front, an easy recommendation is Jean D'Arc. This is a very good traditional JRPG with a fantastic art style and story. It got a decent print run, which makes it much more common than many other PSP RPGs, and can usually be found for less than $10.
The PSP requires a bit of searching when it comes to it's library. But if you are diligent, there are a wealth of great titles that can be had. Also, don't forget that the PSP is compatible with PSN, and the PSP and PS1 digital on-line offerings will all run on it. Find a cheap 8-Gig memory stick pro duo and you're set.