What I did the first time when I made that post was that I did a clean install using a pc/mac, then I went through the setup assistant without restoring from a backup, but then I immediately did Erase All Content and Settings from the General > Reset menu. Then I went through the setup assistant again, and again I didn't restore from a backup. The second wipe is out of habit from old days in IT. After going through these 2 wipes and testing, GPS was just as bad as it was before.
Yesterday, I decided to do a clean install again using a pc/mac. This time I didn't do the 2nd wipe from the General menu. I haven't gone for a drive yet, but so far while sitting in my house, the GPS locks onto my location like it should. Before, I would just get the big circle that covers about 5 houses around me and it would never zoom all the way onto my house. So I'm optimistic now that it should work better while driving. It has only been 24 hours so far.
If this works, then it seems like doing the Erase All Content and Settings from General > Reset breaks GPS, even if you don't restore from a backup afterwards. If this is the step that breaks GPS, then I'm curious if someone tries doing the clean install from a pc/mac then restores from backup if that would work or not.