Ive heard of MapQuest Navigator 5.0, MapQuest Navigator 5.0, GPS Navigation and Traffic - MapQuest Wireless
but its not free. It has a 7 day free trial and then its 4.17 a month there after when you sign up. I use Sprint navigation which is with Sprint (my carrier) so i haven't really tried any other ones other than google maps.
Edit: I just saw in another thread, mention jpsed and amazegps.
Nav4ALL
Try Nav4All. Its a free download OTA. So you can try it out now. Then. You can go from there to see what you like and don't like. Also GPSed is a nice app. Free OTA also.
=8')