I have a copy of Cave Story thats only 2.3 MB on the PSP. In my collection, the following games are under 500MB as uncompressed ISO's:
Cladun 1, Cladun 2, Duodecim Prologus, MegaMan 1, MegaMan X, Tales of the World Radiant Mythology, Harvist Moon Hero of the Leaf, Wipeout, Tokobot, Half-Minute Hero, Brave Story.
In the 500MB-700MB range which you can maybe compress as a CSO to go below 500MB there is:
Killzone Liberation, Sonic Rivals 2, Riviera The Promised Land, Patapon 2, Patapon 3, Burnout Dominator, Valkrie Profile Lenneth, 007 Russia Love, Ys Ark of Napishtim, Ys Seven.
Personally, I would most definately pickup/try Ys Seven if you have not already played/tried it. Its got a fast action-RPG battle system with great music, and you'll be addicted to item collecting.