I haven't really gotten into buying games over the PSN yet, between retail PS3 titles, plus GOG and Steam on PC there's not been time to explore yet another source of games. I also find the store interface semi-clunky, and it's not easy enough to sort through and find games, unless I'm willing to pay for that keyboard extension thing to make searching easier.
So far I only own Call of Duty classic, Wolfenstein 3D, Tales of Monkey Island, and Metal Gear Solid via the PSN store.
I'm feeling like spending $$ with my 40k of holiday money, so please post your PSN must-haves here.

You CAN just plug a usb keyboard in for typing type things, far better to have one for the ps3 than the 360 since you can use the net reasonably well with a ps3.
As for PSN games, the only one I've bought is archer maclean's mercury and I suspect thats psp only. Trine would be a good one to at least get the demo for

PS3:
Bionic Commando: Rearmed - Remake of the side-scrolling NES classic
Fat Princess - Quite fun. Probably the most fun I've had on-line with the PS3
Final Fight: Double Impact - If you're into beat 'em ups
Flower - Supposed to be quite good
Gunstar Heroes - The Sega Genesis classic
Marvel vs Capcom 2 - Great with friends, fun on-line, but the AI gets VERY hard in single play
Prince of Persia Classic - Remake of the original
Sam & Max series
Super Stardust HD - Pilot your ship, destroying asteroids which threaten a nearby planet. Different weapons and multiplay. Actually quite fun.
Super Street Fighter II Turbo HD Remix - Fun if you like Street Fighter, can be played on-line
Trine
PSone titles:
Blood Omen: Legacy of Kain (Dated visuals, but excellent once you get into it.)
Castlevania: Symphony of the Night
Final Fantasy VII
Final Fantasy IX
Final Fantasy Tactics
Legacy of Kain: Soul Reaver (Sequel to the above)
Resident Evil 1, 2 & 3
Suikoden
If you have a PSP there are plenty of good titles available for that as well. Jeanne d'Arc, Dark Mirror, Logan's Shadow, Hot Shots Golf 1 & 2, etc.. Too many to list here.
No doubt, I have missed many. Where possible, I would download the demo first. If I had to recommend only a few, I would say Fat Princess, Castlevania: Symphony of the Night, Blood Omen & Super Stardust HD. Of course your preferences may be different.

PSN Titles:
Critter Crunch
Zen Pinball
Trine
Joe Danger (really awesome game)
Flower and Flow are amazing... well, experiences - they are something different
Super Stardust HD
Wipeout HD
Mashroom Wars - an interesting take on the RTS genre (game is simple, but the difficulty level is pretty high)
Braid - incredible game
PixelJunk Monsters - best tower defence game I've played
Echochrome
Shutter
As for PSOne Classics ... most good games are unfortunately on the US store
I would suggest:
Vagrant Story
all Final Fantasy games
all Crash Bandicoot game
Kula World
Driver

Oh yes! Joe Danger! I had forgotten that it had been released. If you liked Excitebike for the NES, then you'll probably like it.
Actually, Japan has FAR more titles available, but yes. I don't like how Europe often gets the short end of the stick with most companies. :(

Spyro and Alundra are fun games, you should get them aswell.

Wipeout HD
Flower
Flow
Pixeljunk shooter
Trine (if you don't have it for PC)
Worms (if you don't have it for PC)

I can't find Castlevania: SOTN on the store. Don't tell me there's regional restriction bullshit here too.

Yes there is regional restriction bullshit.
I really want Legacy of Kain (the original) but it's not available in the EU.
Check here: http://en.wikipedia.org/wiki/List_of_PlayStation_Store_games

Well I'm pretty damn sure that we don't get Legacy Of Kain
Damn I wish they'd do HD remakes of that series, LoK & Soul Reaver would make a brilliant double pack, be even better as a triple pack with SR2 (Its not like LoK was that big)

The worst case scenario is that you sign up for a North American account and play certain games using it. Unfortunately, you can't transfer the titles to your other account later, and it's annoying to have to switch. All that regional crap IS stupid. At least GOG seems to have gotten around it, but certain other platforms have a long ways to go.

Wipeout HD + Fury!
One of the best games I have ever played. Too bad the online isn't more community-based, because the racing itself is a blast. Especially Zone Battle, that is completely unique and infinitely awesome. Get it nau!

Actually you can play games from one account on any other as long as the account that made the purchase is on the console. On PS3 that is. It's a different story with the PSP since you can only have one account on that.
Before the silly AVS was activated on PSN I could buy stuff from the US store (I got Soul Reaver and Resident Evil 2 and 3 and GEX) and played them on my Polish account just fine.

Nice! Was it always this way? I keep reading posts where people whine about not being able to do that, but I believe you.
Oh and lest I forget. Lemmings isn't bad either. :)

PAIN. PAIN. PAIN. PAIN.