FYI for the other commenters, UnifiedPush can work thru the Prosody mod_unified_push or any server with a up where Conversations (& its forks like Cheogram, Monocles, Blabber) can be a distributor. This has the added bonus of coming with an awesome decentralized XMPP chat server getting to reuse a single connection & single app to server instead of separate ones. Conversations is the most efficient chat client on Android in terms of resources (battery, network, RAM) so might as well keep it lightweight—which you are probably trying to get push notifications from the likes of Signal or Element, but what is the point when you have an efficient XMPP server for your chat needs?

However, I think UnifiedPush might be a bit flawed—as if the startup that created ntfy is pushing others to try to adopt their standard instead of getting folks on board with the older & capable MQTT (which also can be ran thru mod_mqtt on your XMPP server). I am not yet sure if this is a tinfoil take or not.

Why do you not want play services on grapheneos? Doesn't the sandboxing remove any issues with it?

Please update what you chose then, to help the next person.

nfty for applications that support it. your only other choice is microg

Most libre applications implement their own websockets for this. EDIT: some propriety spyware like WhatsApp use those too, can confirm myself, as I unfortunately have to use it on my GrapheneOS owner profile (which ofc doesn't have the sandboxed GPlay services installed; I could technically use it on my profile for personal proprietary apps, but it would be a major pita) ENDEDIT
(unfortunately Proton uses only Google FCM in most of their apps and doesn't publish them on F-Droid or Accrescent)

However, those can take a strain on your battery since every websocket maintains it's own connection.
This is where UnifiedPush in combination with either nfty or Sunup comes in
(EDIT: I use ntfy myself, also Sunup seems to be quite new, so it might come with some quirks; EDITEND there is also a plugin for your own Nextcloud)

Since Unifiedpush maintains only one connection for every app using it, this takes quite a bit less charge to upkeep
(it's explained quite well on their website, which is hyperlinked)

If you are looking for Unifiedpush support on Signal: Molly is a hardened fork of the client and does support it through Mollysocket

EDIT: If you use Telegram there is Mercurygram. As for Matrix clients, I use Element and Schildichat. All these support UnifiedPush

Only thing I have a problem with right now is proton mail. Hopefully soon they will be implementing notifications that don't rely on google play (they said they are working on it)

I don't know about Telegram, but I know, at least with Signal, it should work with web sockets, and allow you to get notifications that way. At least that's how I get my notifications on Molly, which is a fork of signal. While not many applications support it, you might also look into UnifiedPush and ntfy which is a UP app from F-Droid.

I use ntfy from fdroid

It depends for what Apps you need them. Often Apps like Signal or Element support getting Notifications via a persistent Server connection or asking every so often for Notifications. Even tho i could not find any source, i found that this works with Whatsapp(sadly have to use it) too.

It depends. Some apps have their push notifications system but may consume more battery.

You should list what apps

For Signal, use F-Droid and add the repoaitory for Langis which runs without communicating with Google servers, and notifications for Langis are immediate, without a delay.

In F-Droid have a look at Forkgram and Telegram FOSS as a solution.