The issue lies with Google's FCM (Firebase Cloud Messaging) system, so it's not something GrapheneOS can really fix. As far as I know FCM doesn't offer a way to encrypt notification content. Some apps like Signal work around this by instead of sending the message content, they send a little "wake up" notification. This tells Signal on your phone to wake up and it goes and retrieves the new message.
If you don't install Google Play Services, you won't be impacted. But you'll also not get notifications for most applications. There is an alternative push notification system called UnifiedPush which allows you to choose any server to handle your notifications (and even self host it). But it does require both the service and the app to support it, so it's not very wide spread yet.