After extensive investigations, including hours running multiple GPS apps on both iPhone X and older models, Apple replacing my iPhone X, and a ton of Internet research, it is clear to me what the problem is and everyone with this problem needs to be complaining to Apple. The more of us that tell them this is unacceptable, the more likely this will be fixed in the future.
There are two models of iPhone X - one (A1901) has the GPS accuracy problem and the other (A1865) works properly. If you purchase your phone through AT&T, or purchase an AT&T phone through Apple, you will get the A1901 phone. If you purchase an unlocked SIMless phone or through most other carriers, you will get the A1865 phone. Why does this matter?
The A1865 phone uses a Qualcomm chipset (cellular modem and the GPS chip) and these work great. It is the same family that has been in older iPhones for a long time (which is why this has not been a problem in the past). The A1901 phones (AT&T) come with an Intel chipset that seems to have lower specs all around, and in particular the GPS has more trouble connecting to satellites, and even with the same number of connected satellites, the accuracy is about half that of the Qualcomm (accuracy will show twice the distance).
If you are an AT&T customer, I recommend that you purchase an unlocked phone from Apple (this will be the A1865 version), then get it activated on AT&T and you will be fine. In my case, I purchased my iPhone X from AT&T and it took more than 14 day working with Apple to figure out what the problem was, so AT&T won't take it back. Apple also is unable to exchange this for me because it is not from their inventory, so can only exchange for the same model. If you are in my situation, you need to have them escalate this to engineering. There seems to be no other option for us at this point. This is why I am encouraging as many people as possible to communicate clearly to Apple what the problem is so that they will acknowledge the problem and help us. Hopefully it will become harder for them to claim that your phone is the only one that is having this problem.
It is really not cool of Apple to sell us a phone with severely reduced GPS specs and not tell us there is a difference! Apple, please help us with this.