>implementing this in a way that maintains Signal's ease of use for all participants isn't exactly trivial (contact discovery is a big one).

I disagree, as long as it's an OPTIONAL and non-default method. Many people (billions?) have been registering to various messaging services (from email to Skype and all kinds of IMs) and finding each other just fine, without using a phone/phone number.

Phone based authentication has a couple of advantages too, but when a "privacy oriented" messaging app has this as the only option it's fair to point it out.