Well, proton mail for example is available as APK from their download page - no play store required. In fact, many FOSS apps are available as APK downloads from GitHub. You could also use Aurora which enables you to use the play store without login. I am not familiar with it, though.
But again, using alternative play stores adds another party you have to choose to trust in order to use their services - your decision. At least, when using the play store, you can be quite sure about what you download.
While I understand and admire the general goals of ungoogling ones lifes, I also believe it's important to understand what your actuals goals are. When you surf the internet without VPN you leave trails - your IP, MAC address, fingerprinting, and other techniques. Your phone setup becomes less important when you use the same IP (in terms of volunteering data).
GrapheneOS sandboxes apps and gives you control over what apps are allowed to do. You can disable network to all google apps and basically block them from "calling home". It's impossible on stock android. I do not know what data becomes available when using push services, but I faintly remember a discussion which concluded that no actual data is available. As far as I remember it's more like a ping - look, something's going on in app A. But there are way more qualified people here to answer that part of your question.
You are of course right - when you use the play store google is informed about what apps you use. You can circumvent that by using APKs, other app stores or do not install apps which is usually less convenient. It Android gives you the option to use user profiles. So you can split your apps up into different profiles and isolate them from each other if you are concerned.
Another advice is to read the GOS website carefully. Most of the rhings it does (and does not) is explained there.
As a last thought, GrapheneOS is based on Android which is developed by google. While drastically reducing your apps to the ones you really need is a good approach to reduce the amount of data that can be collected about you, it's not a bad thing to use Google Services if you have to. Your privacy improves by taking many small steps, not just by staying away from google apps. In fact the iPhone is pretty communicative and talks to its mother ship way more frequently than you would expect - and you have far less controll over it.