In reply to moffatross:
OK, so it's actually more complicated than I said. Firstly as GPS is receive-only, it can remain on in flight mode. Most phones (including the S4 I think) leave it on, some (including iPhones) turn it off. But maybe you explicitly turn it off?
Secondly, when the GPS starts up, a variety of different things can happen. To get a fix, the device needs to know where the sats are. The information it needs is known as the "almanac". How it gets that information depends on the device.
1) It may remember from last time it was used. Typically remembered data is good for a day or two, though my some phones forget after as little as an hour.
2) If it's a phone and has a signal, it can download the almanac over 3G. This is A-GPS. Clever phones will download an almanac every time they get a wifi connection, even if GPS isn't in use at the time, so they have one ready when GPS is turned on.
3) Otherwise, it has to download from the satellites. Each sat is is constantly transmitting the almanac, and it repeats every 12m30s. If you listen to one sat, it takes that long to get it, listen to two at once it takes 6m15s and so on. If you miss some because the signal is poor, you have to wait another 12 minutes for it to come round again.
If the receiver has no idea where it is, there is a little extra delay, as it searches for sats. If it knows roughly where it is (where it was last used) it starts its search with the sats that would be visible from there. A-GPS can also help with this stage, by giving the rough location of the cell tower.
If you get a fix in less than 20 seconds, it's doing case 1 or 2 above. It sounds like the S4 does cases 1 and 2 well, and you rarely hit case 3. My motorolla defy on the other hand rarely gets a fix within 10 mins if there is no 3G signal.