Sigbjorn out of the box all Location is done solely using OS API and GPS only. This means for initial lock line of sight to the sky for up to 5 minutes to enable AGPS/SUPL almanacs to be downloaded. A lock thereafter should be quicker.
GrapheneOS also provides our own Network Location option under SETTINGS>SECURITY & PRIVACY>PRIVACY CONTROLS>LOCATION ACCESS (Bottom of list)>LOCATION SERVICES
Under both Network Location and Geocoder select GrapheneOS proxy and enable WIFI/BT scanning.
If none of the above works for you then yes installing sandboxed Play Services and following the instructions when tapping on the Play Services is running notification to enable Googles NLP is also an option.
That all being said however I've used Organic Maps and just GPS for all my nav needs without hiccup.