When i used lineageOS+microG on my old phone i could not get Telegram + Signal to work. WhatsApp worked, but push messages arrived hours later or if i opened WA. No idea if this is fixed now.
I'm using MicroG for a year now and didn't have problems with push yet. Signal and WA are working fine, other Apps with push as well. No idea about Telegram, I'm not using that.
Telegram works for me if you use the Google Store version.
I think it's worth noting that Telegram and Signal both have fallbacks in the absence of FCM or microG. I use both daily and luckily am able to daily Android without any of Google's services or microG.