Matrix

Information leaked by the protocol is "what user IDs from what servers are in what groups, replying to what other user IDs how often and at what times". It's the kind of metadata the NSA collected from Americans that landed them in hot water. This is exchanged between servers and copied over to any server with an account present in the room. This information is encrypted by HTTPS in transit, so it's not plain readable, but you have to trust every server in a given room not to leak that information.

Things like profile pictures and display/user name can also be derived relatively easily in common use, though it'll be very difficult to find if you don't join any public rooms and pick a random looking username.

On a protocol level, there's no need for you to provide an email address or a phone number. Some services may require these details to prevent spam/account floods, but you can use Matrix without either. The only reason you're asked for these is that they allow others who have you in their address book to find you, so you can start chatting to people without exchanging usernames. I've opted not to use this info in my account.

I don't know what permissions you found troublesome on Android, though. Everything it asks seems to make sense for a modern messenger with features like video calling and location sharing. There are other apps available for Android, though.

If you use your own server, you'll be in charge of what information you provide, and you can even firewall off servers that you're not interested in communicating with if you want. If you join any public rooms you'll still need to share some info (or the protocol won't work), but you can do things like configure your server to only permit fetching attachments from whitelisted servers. This isn't a standard option, but with some knowledge of reverse proxies it's not impossible to pull off.

Compared to more private, but non-federating, protocols like Signal, Matrix leaks a decent bit of metadata when using encrypted channels. It may even leak more than XMPP, though I don't really use that as nobody I know still uses XMPP. On the other hand, Signal is centralised on one single server, and if that server goes down, your ability to use the app goes down with it. With Matrix, you can just register on another server.

I would say Matrix is secure enough for everyday chat if you enable encryption (and preferably verify the keys of the people you communicate with), but not a good choice for human rights activists or criminals.