1) Crisis Core: Final Fantasy VII
2) Metal Gear Solid: Peace Walker
3) Metal Gear Solid: Portable Ops
4) Final Fantasy IV: Complete Edition
5) Little Big Planet PSP

And...

A tonne of PS1 classics, especially if you live in America.

Tactics Ogre - absolute masterpiece great gameplay and great mature story
Valkyria Chronicles 2 - story might be weaker than in VC1 but gameplay is great
Jeann d'arc- good srpg to start, beatifull story animations and rarely explored motive in video gaming
Persona 3 Portable
Space shooter for 2 bucks - as the name implies it's rather cheap ;) but offers great funny shmup that could be sold as full game

Since no one is saying it.

FFT:Wotl

Also try:
Dracula Undead: Awakening
OMG-Z
ff7 and 9 >.>

There are sooo many good PSP games

Crisis Core
Resitance Restribution
Metal Gear Peace Walker/Portable Ops
Little Big Planet
Ghost of Sparta/Chains of Olympus

There are a trillion more...wikipedia PSP Games list

FFVII: Crisis Core
KH: BBS
Dissidia final fantasy (1 and/or 2)
Star Ocean
Final fantasy IV complete colletion

Seriously, the PSP is the choice handheld for all your RPG needs.

LBP: PSP
Patapon
Valkyria Chronicles 2
Hot Shots Tennis
Half-Minute Hero

These are in no particular order.

I didn't think Crisis Core was that good. I think it was more nostalgia for FF7 than anything else. Or maybe it's just me.

Peace Walker, however, was awesome.

Agreed. The nostalgia factor makes it more meaningful. I played all the FFVII related games and movies so when I got this, I was excited to find out how it all came to be. Still, what I really loved about teh game was the fighting. I always wanted hack and slash Final fantasy, a la secret of mana and CC was that game.

I have never played a single MGS game, being a sony fan. They seem so....slow paced.

I'm kind of the opposite.  I've just started Crisis Core but so far my impression of it is postive.  Same thing with MGS Peace Walker.  I loved every game in the MGS series but, for some reason, I was really let down by that one.  After some initial promise and a couple of cool moments like trying to identify the Quetzal, the game began to feel really stale.  The story and the characters are the biggest part of an MGS game, to me.  In this one, the stealth was too easy and the bosses were all just giant robots.  Maybe if I had taken it online or something.

Yeah, it was perhaps easy. Then again it's a PSP game and you're meant to play a bit of it at a time. I also found the ending with *SPOILER* the Boss following her 'heart' too cheesy even by MGS standards.

I liked the bosses. MGS is about gigant robots after all. I also liked that you can personalise so many things and develop your weapons and items.

In the end, I found the story great with some epic moments, and I liked the characters in general, though I admit some were dull (Kaz. Is he seriously Japanese?). Maybe it's because I didn't expect a full MGS experience and/or because I had nothing else to play or distract me (was on holidays slacking). Couldn't try the online because I no wifi in the hotel.

I do hope they make it more complicated when ported to PS3 though. Playing the game with two sticks would be too simple.