Try this;
1) Install gpstest https://f-droid.org/en/packages/com.android.gpstest.osmdroid/
2) Launch gpstest and wait for a location lock.
3) KILL gmaps.
4) LAUNCH gmaps.
Working now?
If so, it sounds like you need to mess around with the location settings. Gmaps, for some unknown reason, needs to start either with a gps FIX, or have network location enabled.
P.S. if you can get your hands on the apk for gmaps version 11.111.0202, it works withOUT gservices, however, you ALWAYS have to use the hackaround mentioned above for it to work.
I'd also recommend you look at Waze for navigation.... google owns it and it runs off the same database as gmaps, but works better -- no gservices or existing fix required.