To answer your original question, android phones have a built in GPSr chipset in the phone. If you were dropped from a plane in the middle of the Sarengetti with the phone turned off, when you turned it on and initiated an app that used the GPSr, you would eventually (it could take several minutes) get a GPS lock and be able to navigate. Where the internet connection comes in and where a lot of confusion lies, is that android phones use and aGPSr system (Assisted GPS Receiver.) When you have a WiFi connection, the phone uses whatever means at its disposal to assertain your current position very roughly and then quereries the internet for a positional map of the current satellite locations. This does nothing but speed up your GPS lock, but it does speed it up dramatically. After the lock is established, the GPSr chipset maintains a database of satellite positions for your current location and when you try to get a positional lock again, if you don't have an internet connection, it uses the last known satellite postions. This usually speeds up non-assisted locks quite a bit, unless you have moved a fairly large distance from the location of your last lock. I have read that this distance can be as small as 25 miles, but I really don't know for sure. Anyway, in a nutshell, an internet connection only speeds up your GPS location lock.
As for navigation software without internet connection, I have tried a few and find that CoPilot works very well. Your maps are downloaded to your phone and the company (ALK Technologies, I think) does quarterly map updates, which is pretty good. I have found one or two mistakes on the maps, but nothing significant. There are other packages that people like, but CoPilot is my preference. I hope this helps a bit.
BigRedGonzo
