Perhaps the creators of the app could partner with some big providers to allow the app to try creating your account on one of these providers at random (and keep trying different providers if your intended name is already taken on one that it tries).
I also agree with you about discovery of friends being hard unless users provide their phone numbers to a central server, so perhaps there should be an option for that when creating your account. This central database could run by an independent, audited, third party service. I'm not sure who could be trusted in that role (perhaps Let's Encrypt?), or how much it would cost, but it's an interesting thought experiment.
Thats similar to what eMail does, it trades UX for [nothing] (would place decentralisation there if it were not for gmail etc.)
I installed Element, but it required username/password pair. I understand that it's a bit more secure than using phone number+email for first authentication, but it makes discovery of friends too hard. It trades too much UX for security, just like PGP.