Ah so it falls back to GPS, and doesn't pick up the micro-g location.
I have this setting disabled on my phone and it works pretty quickly. But GrapheneOS has options like using proxied Apple location servers which I guess is what mine falls back to.
You don't have the ability to choose other location servers in your phone's settings?