Doukutsu Monogatari ~Cave Story~
It's written for Windows and Mac. Surely, just how primitively this game has been coded, it must be possible. This is the perfect game for porting to PSP, it's fast, enjoyable and has many different endings and events, plot twists and hard bosses.
Doukutsu Monogatari (AGTP Translation)
It's no more than 5 MB maximum, and would keep even the hardest gaming nut challenged. I would love to see this running on a 1.0 & 1.5, and then maybe a 2.0+ with the GTA loader or EBOOT loader. It's gotta be "port"able - this game would be the definitive game port for PSP. I just think it would handle it really well complete with Analog stick support.