Trust on first use: The Achilles heel of centralised messengers

When you first send a message on a new app, you’re trusting that service to send your message to the right person without compromising its integrity or privacy. How can we remove that trust?