For the Google Play Store (GPS), as stated in the GrapheneOS instructions, you can install it, initiate the login process, but do not provide credentials, and simply exit the app. This initializes the GPS libraries to allow for Firebase Cloud Messaging (FCM), which allows for encrypted push messages between the app and its provider, for example, a push message from McDonald's to your McDonald's app. I have two apps that will not run without FCM: myParish - the app actually displays a message that it will not run without GPS; and Toyota - I need this to access remote control features of my car. Aside from those two, I have no need of any Google services.
My guess is that if you remove network permissions, FCM won't work because it must have access to the network to function properly.
- If you want timely Push messages, then Google Play Services has to run with Battery set to Unrestricted: Settings > Apps > Google Play Services > Battery > Unrestricted.
- Auto-fill the SMS Validation Code. Some apps, like Chase, Signal, and others send a validation code to the phone, and Google Play Services has the ability to auto-fill the validation code from the SMS. To enable that, do the following: Settings > Apps > Google Play Services > Permissions > SMS > On.
If your apps work without GPS, my suggestion is this: don't install it(!). American Express and Chase complained that they wouldn't work without GPS, but they worked just fine, and interestingly, I received push messages from them without GPS installed! However, I discovered an anomaly.
CAVEAT
On a fresh install of GrapheneOS, I installed 1Password, Signal, and some other apps, then installed Google Play Store and initialized it. When I realized I didn't need GPS, I uninstalled it but then I ran into a problem: those selfsame apps stopped push messaging!
It seems they enable their built-in push messaging unless they find FCM at some point and then they switch to FCM. But when I removed GPS, which includes FCM, the apps stopped pushing messages, not only that, they stopped messaging - period! I had to uninstall them and reinstall them to get them back to their original messaging status.