GI1 By denying the network permission to Play Services / Play Store, you're making it so most of the functionality it would otherwise be able to provide, it no longer can.
The supported setup for a successful Sandboxed Google Play installation is to have all 3 apps with the network permission, and battery optimization for Play Services set to "unrestricted".
Those apps are sandboxed the exact same way as other apps on your system. The only data they can get is the same way any other app could get data, via permissions, or by having that data passed to it by another app.
GI1 For example the location is not tagged on photos.
Which camera app are you using? GrapheneOS Camera? Google Camera? Which gallery app are you using to check that afterwards?
I believe that if you're using Google Camera, you'll need to use Google Play Location instead of redirecting location to the OS (this is the default), as Google Camera expects to be able to get location very fast and through Google Play. You can learn more about how to do this if you're interested here:
https://grapheneos.org/usage#sandboxed-google-play-configuration
GI1 Is there anyway they could still get the information through other apps that are not Google?
Theoretically apps that communicate with each other via mutual consent can pass data between them, which an app with network access could then send off. If you're concerned about that, you can separate those apps in separate user profiles.
GI1 Also does the phone store my play services data?I am concerned if I accidentally turn on the network all my history would be uploaded to Google.
That would probably require you to be logged in to a Google account, at which point you could disable most of that functionality. That said, Play Services will need some data in order to provide you with the functionality you need. If it doesn't have network, it won't be able to do so anymore, and if you turn it on, it'll have to forward that data appropriately.
This is also the case with alternative implementations like MicroG, you can't avoid that if you use apps that require Play Services functionality. Hell, some apps don't even require Play Services, MicroG, or anything else. As an example, Google Maps can function perfectly without anything else being required.
By using GrapheneOS, you're already ahead of the curve, and Sandboxed Google Play is designed in a way that makes using it secure and arguably private, provided that you're okay with the service having access to the data it needs to provide you with the functionality you're requesting of it (which again, isn't really possible to avoid, even with other approaches).
I hope that helps!