I have the Garmin GPS app on my storm and it works great. It is all most identical to my Nuvi in the way it works. It is $99.00 but you only pay once....no monthly fees.
I have Trapster, which has GPS built in, GPSed, Blackstar, amAze, Nav4All, and TelMap Navigator. amAze seems to be the best free gps program out there, but I haven't had much of a chance to use all of these to truly pick out which one I like the best.
TeleNav- on some phone carriers they offer it for like $10/month. With anything, get ahold of their retentions department and try to negotiate a good deal =)
The Curve through Verizon has the GPS locked except for bbmaps..VZNav is availible for9.99/mo and works great..The curves GPS is locked to outside 3rd party apps.