With the Galaxy S you can hack/mod it to enable Navigation with Google Maps. I have a Galaxy S variant, Samsung Captivate and I have it working, even the text to speech works. I think you can set up a trip, say via WiFi downloading all the required stuff from Google Maps, and then you would not require a subsequent data connection, just enable GPS.

The hack was easy but it does require root access. There is a "one-click root" app. for the Galaxy S. Thanks to member Thaicbr for posting this originally.

Relevant links:

http://android.modaco.com/content/zte-blade-roms-rom-customisation/339172/you-can-use-google-maps-navigation-in-unsupported-countries/

http://forum.xda-developers.com/showthread.php?t=1007132

Thanks for the info about Galaxy S, the problem is it does not work with garmin map, others might be interested as android is gaining popularity, I will definitely look into it for my next purchase since I have already bought Nokia N8.