XMPP/Jabber comes to mind. You can self host or pay for hosting on a service like Snikket. The protocol supports OMEMO encryption and you can use whatever client you want (Cheogram, Dino, Gajim, etc) on any platform like android or linux. Cheogram is even coming out with a web interface for it, and it supports calling and video calling.
Threat model wise, whatever server you pick would have to be targeted directly, and would therefore be immune to sweeping regulation that directly targets big hitters like Signal. And if you pay for servers outside the EU, even more so