There are two parts of this, as poncho already noted in his comment:
- protecting the confidentiality of the message against a man-in-the-middle;
- protecting the integrity / authenticity of the message against a man-in-the-middle.
The first protection can be achieved by making sure that the public key of the key pair used by the receiver can be trusted. That is: the sender must be sure that the private key is under control of the intended receiver.
The second protection can be achieved by signing the message before encryption using a separate key pair used by the sender. To be able to verify the message the receiver of course needs make sure that the public key of the sender can be trusted.
Using a MAC or encrypt-then-sign won't work. The attacker could simply strip off the MAC value or signature and replace it by its own value.
Finally you may have to make sure that replay attacks cannot be executed. Any additional (symmetric) algorithm must be used correctly as well of course. Just getting this part right doesn't suddenly protect the entire system.