The answer to most everyone question you’re asking is just, “public key cryptography”. It’s kind of disheartening to me that such basic 1990s tech as implemented by Phil Zimmerman is now obscure enough to merit questions like this.
Both parties exchange public keys through the central service. Only the possessor of the respective (on device, Secure Enclave ideally) private keys can decrypt the messages encrypted to the public key. The process can also work in reverse, encrypting with the private key so only holders of the public key can decrypt: this is called “signing”.
No, it's not at all this simple. This is why so many "e2ee" apps like Telegram are bogus, they ended up prioritizing UX over security because there are many places where you can't pick both.
The fly in the ointment is that they control the software and updates to that closed software so can short circuit that with appropriate pressure.
And how does one verify that the public key received belongs to the intended party, rather than a mitm?
If the answer is blind trust in a third party that runs the messaging service then I suspect that you can guess what the people asking those questions are really asking.