ThisOldGuy Play services is unrestricted and has notifications.
ThisOldGuy There's been reboots and upgrades and cache clearing and reinstalling of those apps without any change.
Do you have Settings > Security & privacy > Private space > End session immediately on lock enabled, and are you locking the private space when you're finished with it? If you've made sure Play Services has unrestricted battery and you've reinstalled apps, then I'd expect them to work.
A couple other things that you can check would be to make sure Play Services has the network permission. Also, if you have a VPN set up or some app or DNS set up to block ads, trackers, etc. that the app/VPN/DNS aren't blocking connections to Google.