You can't get a man-in-the-middle (MitM) resistant channel out of a vacuum.
You need some common knowledge beforehand. Luckily all one needs is a shared trust relation.
Suppose the server Steve trusts Carol, suppose further the client Charlie trusts Carol aswell.
As an example I'll give a simplified TLS-RSA key exchange because it's particularly easy.
First Steve needs to submit his public RSA key to Carol for certification. Carol digitally signs Steve's key and embeds in an certificate tying his name ("Steve") to his public key. It is assumed that Charlie can verify Carol's signature. This only needs to be done once.
Charlie now initiates a connection to Steve containing the request for communication and specifying the available cipher suites Charlie supports. They contain informations on how to encrypt and authenticate the data after the key-exchange is finished. Further a random number will be sent in the initial message. Steve will answer with his selection of the cipher suite and his random number.
In the next step Steve will send his certificate. Charlie will verify the certificate by checking Carol's signature and if it's valid will accept the key to be from Steve. Now Charlie randomly chooses a random "pre-master secret" and encrypts it using Steve's public key. He sends this to Steve. Charlie now derives the master secret from his random number, the pre-master secret and Steve's random number.
Now Charlie sends a message indicating that from now on the selected encryption methods shall be used. He finishes this messages with a message authentication code (MAC) on all previous data using the master secret as key.
Only Steve will be able to decrypt this pre-master secret. He decrypts it and derives the master secret himself. Now he verifies the MAC he received. Next he sends the message indicating he's ready to use encryption. He finishes with the same MAC (on all previous data).
Charlie verifies it and can be assured that no MitM attack has taken place because only the holder of the private key could have sent the MAC and he knows that Steve is the holder of the key because Carol confirmed it via the certificate.
Now a standard pre-shared key data exchange protocol starts (a.k.a. "record layer" in TLS terms)
TL;DR: You use digital signatures to bind public keys to identities and use those keys to construct secure key-exchanges.