I do agree about being linked to your phone number - doing it that way means not considering a lot of people's valid threat models. They are working on moving to usernames, though. It's in beta now.
It doesn't say how it works. If Alice's phone can tell whether her contact Bob uses Signal without Alice and Bob doing any sort of a priori cryptographic exchange, why couldn't Signal itself do whatever Alice's phone is doing?