Earlier quoted context omitted.
The Telegram client is available on F-Droid, so you can still use it even if you opt-out of the walled garden.
Unfortunately Telegram-FOSS from F-Droid doens't have GCM support so won't be notified about DC updates via push messages. I this particular case the centralization around the push service of google actually helps.
I always get notifications about Telegram messages on my phone at around the same time (within a second or so) as I get the notification on the web client.