This can be solved with a backup that store the address book (but not in the cloud, please!). Signal for Android already have a safe and encrypted backup feature, I use it to keep my message history safe.

Not being forced to add a contact to the phone address book is an extra advantage, as address books are one of the first victims of spyware apps...

Also, with usernames and a desktop app, there is no reason to require a smartphone at all! Seriously, my Android phone is the least secure platform that I use at the moment (lots of proprietary stuff, spyware prone, ...)

Wait what? You specify a username and at least one user-chosen "challenge" in order to verify ownership of it -- phone number, email, password, TOTP, public key which is stored with Signal. Then when you register a new phone you verify the username exactly like you verify the phone number but with the user's challenge.

Like it's more effort, but not some intractable problem, at least stated like this.

I feel like that issue could be solved by creating a random unique say 16 digit UID that users could then add as a phone number for contacts. As long as it does not map to a real routable phone number a phone dialer won't have issues if you call it by accident. Smarter dialers like that in calyxos could recognize it for signal calls if it has a unique prefix.

They could even sell existing users UIDs so they could share their contact info without sharing their phone number if they so desired, e.g. via a website. If they charged some nominal fee users could reset their UID. Maybe with escalating prices if done in short succession to make revenue and discourage abuse.