They MITM the key exchange step at the beginning, and now they do have the keys. The thing that prevents this in TLS is the chain of signatures asserting identity.
You can have TLS with TOFU, like in the Gemini protocol. At least then, in theory, the MTIM has to happen the first time you connect to a site. There is also the possibility for out of band confirmation of some certificate's fingerprint if you want to be really sure that some Gemini server is the one you hope it is.
You can not MITM a key that is being exchanged through Diffie-Hellman, or have I missed something big?
Yes, Mallory just pretends to be Alice to Bob and pretends to be Bob to Alice, and they both establish an encrypted connection to Mallory using Diffie-Hellman keys derived from his secrets instead of each other's. Mallory has keys for both of their separate connections at this point and can do whatever he wants. That's why TLS only uses Diffie-Hellman for perfect forward secrecy after Alice has already authenticated Bob. Even if the authentication key gets cracked later Mallory can't reach back into the past and MITM the connection retroactively, so the DH-derived session key remains protected.
If we know each other's DH public key in advance, then you're totally right, DH is secure over an untrusted network. But if we don't know each other's public keys, we have to get them over that same network, and DH can't protect us if the network lies about our public keys. Solving this requires some notion of "identity", i.e. some way to verify that when I say "my public key is abc123" it's actually me who's saying that. That's why it's hard to have privacy without identity.