You're not wrong to notice the VPN side: what are most of our examples? Malicious service providers! What's a VPN? An intermediate service provider!
I did say decrypt, and I did really mean it. SSH and TLS are not nebulously "hard to decrypt", otherwise we wouldn't use it because our servers couldn't decrypt the communications from our clients. They are hard to decrypt if you don't know a shared key. In MITM there are two shared keys: the client shares one key with the interceptor, the interceptor shares another key with the server. That's why the interceptor can decrypt.
Furthermore if we're talking the normal open Internet, the interceptor-server negotiation is dead simple because it looks to the server like any client-server negotiation. If you let anyone on the Internet access your pages through TLS, there is no hope to catch MITM on the server-side. It has to be defended client-side.
There is fundamentally no way to stop an interceptor who you have to send messages through from throwing away those messages and sending you the reply, "why yes, I really am https://mail.google.com/, here's my public key, let's negotiate a shared key so that we can talk in secret." Nothing. Because, you don't have an encrypted connection before you've negotiated that shared key. You aren't encrypted before you're encrypted. So for that setup phase, there's no way to stop them from throwing out those packets and sending that reply; we can only hope to detect that they are lying.
Now they are only telling us one thing, "here is my public key", and we want to know if they are lying about that. We have come up with exactly two strategies to deal with this client-interceptor side.
1. Like SSH does, admit defeat: but only for the very first connection. The very first connection, yeah, that could be intercepted. Then I will store your public key forever. Every time afterwards I will either use that public key, or else I will fire up the klaxons warning my user, and they will have to manually approve connecting and storing the new key. And that means you'll have to keep intercepting my traffic--even if I take my laptop to a different location or whatever--or else I'll find you out eventually.
2. Like TLS does, communicate some way of authenticating that public key through some other mechanism than the current internet connection. This usually happens quietly as part of downloading a web browser: that browser comes with a list of public keys of authorities whose digital signatures are trusted by the browser for authenticating public keys. If a site just sends me their public key? Forget it! They have to send me their public key plus a certificate issued from one of these authorities, saying "Yes, that is a valid public key for that domain," signed by a private key whose public key I know and trust. As long as I can verify digital signatures and they cannot be copied, I am good.
These are called "Trust on First Use" and, well, I'm not sure what you'd call what TLS does. Something like an "out-of-band" configuration of a "web of trust" I suppose. So those are the only options we've gotten working at scale, TOFU and OOBWOT.