You're partly right. A gps also needs to download ephemeris data in order to calculate your position. This can either be done directly from the gps satellite or using the data connection (assisted gps) If downloaded from the satellite, you need really good signal strength and it can take 2-12 minutes. If downloaded from the network, it's almost instant. Assisted gps can also offload some of the signal processing to the cell tower to improve lock time and location accuracy. So it's not just the map data that gets downloaded from the network.
Once the gps has locked on, you can usually maintain a lock after you lose network connectivity. But if you're driving through a canyon or something where there's significant multi-path, you will probably lose the lock. By using assisted gps, phone makers can get by with using weaker gps antennas than you would find in a dedicated gps unit like a garmin etrex.