So what's the solution here? Every user running their own coordinator, all of which communicate with everyone else's coordinator in a decentralized manner, much like the bitcoin network itself?
It could work, at least to those who're willing to run their own, otherwise we'll fall back into trust problems. Practically, it should be very easy to make it work, and even if you didn't run your own node, and it'd provide you the same level of privacy. (Assuming you're doing everything through Tor)
A coordinator's server implementation could come pre-installed in one of these Bitcoin node OSes as well, to make it easier for the masses. Just as Lightning's peer discovery.