Spent time pounding my head on a desk to figure this out, but turns out even if you have your app.json setup with the apiKey for Google Maps API, you still need one more thing:

<MapView
    ref={mapRef}
    style={styles.map}
    initialRegion={initialRegion}
    initialCamera={initialCamera}
    onRegionChangeComplete={onRegionChangeComplete}
    provider={PROVIDER_GOOGLE} 
    toolbarEnabled={false}
>

Where

provider={PROVIDER_GOOGLE} 

is the key.

This was in particular with an expo project, so after adding this I was able to do an npx expo prebuild and expo run:android and be off to the races.