Make a list of privacy-preserving things Signal does: the elaborate privacy scheme for user profiles, the special privacy proxy for GIF sharing, the envelope certificate trick they just introduced, &c.
Then go see what other messengers do to provide the same UX.
Depending on the messenger you pick, you will likely not have to give up your phone number, but you will leave the messenger operator with a log of everyone you've communicated with.