legreteco I can second this fix though, even if you say it shouldn't be needed.
I've had location issues with mutliple apps, mainly a german speedcam app and the "Yale Home" App to control my smart lock.
Following mynameis_'s advice, I enabled location for the play services and it instantly started working - like within a second of me enabling that, the Yale Home app notification came up showing working location access. The speed cam app also has had no issues since.
And on top of that, it fixed my awful battery runtime on Graphene, I didn't even make it through half the day before. Now I assume that the yale home app was at fault, because it probably kept trying to get location even though it couldn't, and the play services not having location access isn't something it was programmed to consider?
But yeah, mainly posting this for others that might run across the same issue, even if play services shouldn't need location permission, if you've got location/gps issues, give it a try.
I'm glad I found mynameis_ 's post, because I was about to leave grapheneos and go back to stock pixel over this issue