I'd have to recommend Gundam Battle Universe and Macross Ultimate Frontier if you like mech games. Mortal Kombat Unchained is a pretty decent beat 'em up. Ninja/stealth games are well represented - there are four Tenchu games and Shinobido (which was done by the same people who made the original Tenchu games). Not to mention the vast back catalogue of PS1 games.
You might have observed that a lot of the replies so far have a ton of JRPG recommendations. It's a strength of the platform, and there are a lot of exclusives, but there are a lot of stinkers too. But I bought a PSP initially because of that part of the library. I've probably spent more time on the Monster Hunter series than with any other game on the PSP. If you're not familiar with it, imagine Phantasy Star Online with loincloths, and giant boss monsters running around everywhere. The difficulty level is really high and unforgiving, but if you're into that then Monster Hunter is definitely something you have to experience. Believe it or not, for me the other defining game of the platform would have to be Pangya Fantasy Golf. It's based on a Korean MMO three-click golf game that mixes fantasy elements into the play mechanisms, so you end up having dwarves and elves whacking at magical balls on a volcano. As far as other platform-exclusives, you don't want to miss out on the SRPG titles. Stuff like Disgaea and Final Fantasy Tactics have been ported to other platforms already, so you want to check out hidden gems like Mytran Wars and Field Commander. Also in that same genre is Valkyria Chronicles 2, the excellent follow-up to the PS3 game.
