The problem is that the DNS contains an MX record that says where to deliver email for a domain. So when a sending server wants to send, it looks that up. Then it looks up the received name as an A/AAAA record to find the IP address to connect to.
So we're already relying on DNS, which can be poisoned.
The "fix" for DNS poisoning is not DNS-over-TLS/HTTPS because that basic problem isn't solved.
If we secure DNS against tampering/poisoning, then the same infrastructure can deliver public keys and other information safely as well.
I'll mention that the MTA-STS policy includes a list of permitted MX, so a poisoned MX record would be detected. But you are still correct about "first email to a domain" concerns; MTA-STS does not offer protection when the policy isn't in the cache.
There's some obvious improvements we could consider, like a community list of domains known to support MTA-STS, and mail servers pre-warming their caches. That gets us something closer to the HSTS preload list, which protects the first connection to a domain. MTA-STS is a reasonable foundation for future work.
It's also really worth remembering that the current best practices for email are unencrypted connections, skipping TLS cert verification, and sometimes DANE. A solution that protects all but the first email is a big step forward.
I think this analysis doesn't factor in the MTA-STS cache. While an attacker could block the MTA-STS records with a DNS cache poisoning attack, they'd need to perform the attack persistently to prevent the policy from being cached. This greatly reduces the window of vulnerability and complicates the attack.