Cell phones get around this by downloading the almanac from the internet. Standalone receivers also keep the almanac in nonvolatile storage, but the almanacs eventually go stale if you leave the receiver off for too long.
The satellites only know their own position to a certain precision, and there are only so many bits to express it in the data packet. More bits wouldn't make sense because the measurements aren't that good in the first place.
So what you get "live" is naturally limited by both of those things. Single-frequency unassisted solutions are usually good to a few meters, dual-frequency to a meter or so.
But ground stations can determine, after observing the satellites for a long time, where they _were_ to a much higher accuracy. It's a complicated process involving a whole network of ground stations, whose own positions are precisely surveyed, etc.
The product of that network is known as "precise ephemeris", and it's available in an "ultra-rapid" (3-9 hours later), "rapid" (24 hours later), and "final" (13 days later) version. With these data, the initial observation can be post-processed to get very good solutions. Down into the millimeters.
The RTKLIB manual has a lot more detail if you're curious.
Even sidestepping the internet just handing you a full alm+eph dump, modern standalone receivers can perform a cold-start much faster than their predecessors, because they have huge numbers of receiver channels available. The system operators cleverly offset the almanac being transmitted by each satellite, so if you can receive several satellites at once, you can start writing your almanac with several pencils on the page writing different paragraphs, as it were. Finish the page very quickly.
In the early 90s, it was common for a GPS receiver to have just 4 channels. So a blind search through all the satellite PRNs could take quite a while, and since the receiver didn't know where anything was yet, Murphy's law guaranteed that any satellite it did get a lock on would soon disappear over the horizon anyway. It took agonizingly long to get lucky and hit a bird just coming into view, so you could get whole messages from it and start filling in that table.
And of course any obstructions that limited your sky-view just made it worse.
By the late 90s, 12-channel receivers were fairly common, my first was one of these. This greatly increased the odds of getting useful satellites in a reasonable period of time, and on cold-start it would get a fix pretty reliably in 15 minutes, sometimes less.
In all cases, if the user could give the receiver a hint of the current time (within a few minutes) and location (within a few degrees), as soon as it got part of the almanac it could start figuring out which satellites must be behind the Earth right now, versus which ones would likely be overhead, and make much better use of its receiver channels to shorten the TTFF. Additionally, being able to estimate the Doppler shift greatly shortens the lock-on period.
Today's receivers don't even have discrete radio channels in the old sense, they just have a wide RF front end and then slice the data into digital correlator pipelines, achieving hundreds of virtual channels. True "all-in-view" reception is possible even with four full constellations aloft, and it's nearly magical how good they are. Cold-start times under a minute in some cases.
HOWEVER.
A survey receiver, whose data is being post-processed, need not even calculate its own position. (It probably does, since that costs nothing once the data has been received, but it's not strictly necessary.) It just records carrier-phase measurements and pseudoranges, along with clock and doppler info, in (or later converted to) a format called RINEX. The surveyor just keeps it in one place for a while, marks down "3:32pm-3:38pm, marker C", and then moves to the next point. Later back at the office (once the precise ephemeris comes out), the RINEX is crunched with that better data, and solutions are derived which allow the surveyor to say exactly where Marker C actually is.
This is better than doing it in real time, because the ephemerides available in real time just aren't that good. Only by measuring with a network of ground stations, can the better ephemerides be calculated, and then applied to the observations.
There's also RTK and correction networks, which deserve mention:
Real-Time Kinematic is called that because it tells you about distance and motion, the kinematics, _relative to a nearby base station_. If the base doesn't know where it is, the rover doesn't either. So the base is usually surveyed first, using the techniques outlined above, and then that surveyed position is combined with the kinematic differences, to derive the rover's precise position. It requires a data link between the base and rover, though that's gotten dramatically easier in the last few decades...
Correction networks do all of that, over a wide area, providing a "virtual reference station" nearby to wherever you need it to be. The corrections are transmitted typically over a separate data channel (often on leased L-band satellite time), and applied by the receiver. Some are available over the internet as well, if cellular signal is easy to come by wherever you happen to be. I don't know as much about these as I'd like to.
At that time the signal was intentionally degraded in a process called Selective Availability (https://www.gps.gov/systems/gps/modernization/sa/). I didn't have any experience with that.