Was in the same Situation. Tried calyxos and lineage os with microg but there were always issues. I wanted a phone that works, so I bought an iPhone. I know that is not at all the best way to have privacy, but it works. I try to use as much open source and selfhosting as possible to minimize the data Apple gets. https://github.com/dkhamsing/open-source-ios-apps
I now have a pixel with grapheneOS but unfortunately it is the same problem with the location in some apps.