From cold start. Most starts are not cold. The phone knows where it is, approximately, what time it is (within a second or so, from built-in RTC), and orbital parameters of the satellites overhead (maybe without the latest corrections).

My Garmin watch gets a GPS lock in way less than 5 minutes without any cellular connection.

Actually, your Garmin probably gets A-GPS data uploaded to it via the app.

I think that because Huami/Amazfit/Xiaomi smartwatches already do that. We know this from reverse engineering efforts in Gadgetbridge, but support for Garmin is still new and so there isn't as much info about it; either way it probably works in the same way.

My first GPS Garmin watch used for running back in 2011 didn’t have an app and didn’t have any cellular signal. I put it on my wrist and started running. I don’t remember it taking more than a minute to get a signal.

No, it's not paired to the phone, and there is no Garmin app on the phone either.

That’s just not true for modern phones. I use iPhone on hikes without cellular connection and GPS lock is instantaneous. Organic Map app is great for hiking.

You're talking about something very different called a hot start. The GP is discussing time to fix in a cold start scenario. You'd only see this on a phone that had been powered off for months, or "teleported" hundreds of miles away. In this scenario the receiver has to download the new time, new ephemeris data, and a new almanac (up to 12m30s in the worst case) before it can fix. Depending on the receiver, there may also be a delay of several minutes before it enters cold start mode.

If the receiver has recently (last few days) gotten a fix and hasn't moved too much from that fix, it'll be in at least warm start mode. It still needs to download ephemeris data, but this usually takes 30ish seconds to fix.

If the receiver has seen a fix very recently (last few hours) or a recent network connection, it can fix from hot start like you saw, which only takes a few seconds and may not even be observably slow depending on how the system is implemented. Phones go to great lengths to minimize the apparent latency.

You reminded me of my first GPS, which connected to a laptop via RS-232:

https://www.bevhoward.com/TripMate.htm (Not me)

Back then, just getting a GPS fix at all was exciting. Then driving around with it propped on the dashboard or rear window.

The sibling response here covers all of the points I would say. Scott Manley has a nice video covering the history of GPS and how it works, well worth a watch https://www.youtube.com/watch?v=qJ7ZAUjsycY

It's not as simple as you think.