Most PUSH notifications use Google's FCM protocol in the background, which means you need some sort of Google or Google spoofing layer to receive them. That's just the nature of current Android since most people use stock and most developers assume you're using stock.
Though, this doesn't apply to non-push notifications such as alarms, reminders, pull notifications (supported by some email clients, RSS readers), etc.
There are also some apps that use alternative push notifications such as UnifiedPush, but you need to set this up yourself (worth looking into if interested). Some apps support their own notifications by opening up a websocket that maintains a persistent connection to the app"s server rather than using Google as an intermediary, though this will be worse for battery than just running sandboxed play services if you require push notifications for more than 1-2 apps. Most people that do this will use it for Signal/Molly. (Molly notifications are much better for battery life) and only if they're insistent on not having sandboxed play services since Signal supports FCM by default.
Ultimately, you have a few choices.
Live without push notifications on certain apps.
Use sandboxed play services
Use alternatives to fill the gap, like Thunderbird/Fairemail for pull notifications, You've got mail (found on F-droid), Unified push, websockets
Compartmentalize your apps to multiple profiles/private spaces so you can separate out the apps that require play service notifications and those that don't (always running multiple profiles in the background will usually be worse for battery life than a single profile running play services).
As for installing apps, here are some helpful pieces of knowledge to help you strategize.
Play Store is more secure and more reliable than the Aurora Store. You can attempt to create an "anonymous* Google account and only use this on a profile with an always-on-VPN if concerned about privacy.
There are alternatives like Obtainium, Accrescemt, and F-Droid, though many on here discourage F-Droid due to security concerns (such as F-Droid apps sharing the same F-Droid signing key instead of being uniquely signed by the developer - this is why they recommend the play store or getting apps directly from the developer's repo via obtainium).
Sandboxed play services is significantly more privacy friendly and secure than normal play services running on stock, GApps, microg, etc. Unlike those, GrapheneOS' implementation of sandboxed play services does not have system level privileges to do whatever it wants on your phone. It's contained like every other app which means it only has access to the permissions you give it and it has the ability to communicate with apps that have explicitly agreed to communicate with it (via interprocess communication - such as Google logging you in across Google apps or apps choosing to support FCM). To get reliable FCM notifications on GrapheneOS, play services only requires 2 permissions: network and notifications as well as setting it to have unrestricted battery usage in the background. You can use an always on VPN if you're adamant about not sending your ip address to google.
Android security features do not allow you to downgrade an app to an older version without first uninstalling the app. The signing key must also match for each update. As long as the signing key matches, you can update from any source you want.
If you do not install from an app store that verifies the signing keys for you, such as play store and accresscent, you need to verify it yourself manually. This means using App Verifier if it's logged on their database or hunting down the keys yourself and either using app Verifier or adb to manually confirm the app you're trying to install matches the signing key from the developer. GrapheneOS doesn't expect new users to do this which is why they recommend the play store. Developers also often don't make their keys easily accessible. As far as the Aurora store, from my understanding, it's considered less secure since it does not provide play protect and it uses a shared Google login for its "anonymous" login option, which is a security concern. Again, it's not that it can't be used, but grapheneOS cares more about security than questionable privacy benefits.
Apps are installed only once on the device regardless of how many profiles or private spaces it's installed on. But each profile only has access to the apps that you allow them to have access to and the apps can only see that profile versions' app data.This is important to understand since it directly ties into the previous bullet point. Meaning:
If you update an app on one profile, it updates it on all profiles.
If the signing key does not match the signing key of the app on another profile, you'll be blocked from installing/updating it. This happens frequently when switching between F-Droid apps and developer signed apps as explained previously.
You cannot downgrade an app without first uninstalling it from ALL profiles.
You can update an app even if it's disabled.
You can install apps to other profiles if the app is installed on the owner. You can similarly install apps to a private space if the app is installed on that private space's profile.
With this information, you can get creative.
So for example, some people will choose to use the Owner as an app installer/updater. Install the app from play store or other source, disable permissions, disable the app, and then push it to another profile from the multiple profiles settings menu. You can simultaneously remove unrestricted battery usage on play services on that profile or even disable it temporarily if you're comfortable with manually checking for updates.
This also means that if for some reason you're having an issue updating an app, you can get around this by installing the newest version on another profile.
You can also use a private space to update previously installed apps as well, though installing apps for the first time would still need to be done in the Owner if you want to push it to multiple profiles without having to manually install it on each profile.
Having said all of this, the simplest strategy especially for new users is to just use a single profile with sandboxed play services. All of this stuff is very cool (well, I think it's cool), but it's pretty overkill for the average person's threat model who are just looking to minimize unnecessary data collection.
And this ties back to something else you said: degoogle. GrapheneOS is a security focused operating system with privacy benefits. It's technically degoogle by default, but its goal is not strictly to degoogle. Too many people fall into the trap of thinking they need to completely remove Google, which is a very narrow and impractical focus. There are so many privacy and security threats out there and Google is not even the worst player out there, which degoogling not only does nothing to protect against, but also may cause further issues by setting you up with insecure tech in the name of degoogling. You're also still not going to successfully degoogle even if you have a degoogled phone - Google (and other privacy concerning companies) control the internet regardless of which phone OS you use.
GrapheneOS, at least according to how I see it, gives you the ability to take advantage of things Google offers (like Pixel hardware security features, play services, camera quality, chromium performance and security, android itself) while at the same time significantly improving security and significantly limiting the scope of Google's control over your phone and data.