While the PSP's got quite a few visual novels, most're only in Japanese, unfortunately. The only real visual novel I know of on the PSP is "Hakuoki: Demon of the Fleeting Blossom", though I don't know too much about the game, besides that it's an Otome game with samurai and a decent bit of action scenes. From what I hear, it's pretty good, though I've got no clue how much appeal it'd hold for someone looking for a story moreso than a romance.
Also, while it's on the Vita rather than PSP, there's "Zero Escape: Virtue's Last Reward", which is more of a suspense/mystery type of game. Haven't played that one yet, but I hear it's supposed to be pretty good; It's also the sequel to "Nine Hours: Nine Persons: Nine Doors", on the DS. I dunno if it matters much whether you play 999 first, though 999's a really good visual novel in itself, so it may be good to start with regardless.
Besides those two, most of the translated visual novels I know of are either on the PC or DS, so those would be the main platforms to check into if you just want visual novels in general.
Danganronpa is getting a fan translation, that requires custom firmware and what not though. I haven't looked into other fan translations to there may be more. Also I think Disgaea has a a visual novel spin off as well, which has been translated.
As the above poster said DS or pc is probably your best bet. Pc especially although a lot of it has 18+ content, it has a good fan translation scene though.
Although Hakuoki is an Otome game, it doesn't really focus very much on the romance aspect. I'm a fan of Otome games, but I think it has appeal for people who aren't into them either. That's probably why it's one of the two that have ever been localized. --- UFP- Unidentified Flying Pancake. The O-Men! Saving the world one cheerio at a time!
*eyes my copies of Never7, Ever17, Umineko, Monochrome, Memories Off, Kanon, Air, Snow Portable, Steins;Gate....*
Hmm, I think the title for 'coolest PSP Visual Novel' is going to be a more fierce competition than just declaring the hottest new thing King.
We're talking "in English," though.
...But even if we're not, Corpse Party might be hard to beat -- at least, for me. ;)
Well, of what he mentioned, Never7, Ever17, Umineko, Kanon, and Steins;Gate all have completed English translations on the PC. They're also all pretty good games, though I'd especially recommend Ever17 and Umineko, which're two of my top picks not only in terms of visual novels, but for stories in general.
While they are decently different from Corpse Party, both feature survival situations with a decent bit of mystery and suspense, with Ever17 focusing on a group of strangers trapped in an underwater themepark after the place goes into a lockdown for unknown reasons, while Umineko focuses on a family and a couple servants who meet on the head's private island to discuss his inheritance; they then get trapped on the island due to a typhoon, and murders begin to occur by an unknown hand shortly after.
The only bad thing about those titles is that they have a bit of a slow start, but both have a little more to them than the plot would intially hint at, and both are really, REALLY good once they get going.