Buy a phone that accepts Lineage and install Linage without Google Services. Alternatively, buy a Sony phone and install AOSP on it. You can even use Micro G to get improved GPS accuracy.
You could also buy a Galaxy S3 and install Replicant on it or buy a SailfishOS-compatible phone.
>muh baseband!
That's just a teoretical attack. No proof of it being used exists.
Even then, if the proprietary baseband bothers you, your only choice would be the Librem 5 with the baseband switched off. Or any phone with Airplane Mode on.
>muh GPS!
GPS doesn't send any information to the satellites. The phone receives the coordinates of each satellite and then calculates on the phone the longitude and latitude it's at. Now if you have Google Services on the phone it will retrieve data from Google's services about your nearby phone antennas and WiFi networks to better triangulate your position.
You can bypass this and still get the improved position by using Micro G.