First of you should downgrade your PSP so you can run emulators on it. There are so many out right now, and a lot of them run full speed including GBA, Sega CD, Stepmania, Neo Geo etc etc. Some of them have adhoc multiplayer support too.

Anyway, when it comes to actual PSP games I recommend: Crisis Core, Puzzle Quest, Jeanne d'Arc, Valkyrie Profile and all the Falcom games as far as RPGs go. Other than that you should check out: Castlevania, Space Invaders Extreme, R-Type Command, Flow, all the Metal Gear games and the Capcom and SNK arcade ports/compilations.