I'm on google pixel 8 pro. Google play is installed (battery optimization is off, location permissions is on). I can use google maps and the running app "RunnerUp" without problems. Both can find my location. This doesn't work with OpenStreetMaps. Also: battery optimization is disabled, ALL permissions are granted). When i open the app and try to find my location there is the error "position is unknown". This happens when i'm outside or inside (everywhere). The problem occurs since installation of the app (never worked). As i understand OSM doesn't need google play to work.
For me it doesn't look like a problem with the app it looks like a problem with Android/GraphenOS or the way the apps gets the information needed to work.