What it doesn't do, DNSSEC tried to fix (chain of trust, negative acknowledgements, etc) but for some reason, it was considered "too hard", in the same way that IPv6 was/is.
It also didn't solve the security of the protocol because the queries remained unencrypted, even if the data returned was guaranteed to be accurate.
However, the result is things like DNS-over-https which essentially requires edge users to trust closer-to-the-center resolvers to maintain the security of their queries.
So we need a trusted, encrypted protocol to query a trusted, secured, distributed naming service.
Using https to a well-known source that relies on DNS for location adds very little to the security against poisoning a DNS cache.
So "storing public keys" isn't the easy part of the problem. The PKI should be in-built with the naming service because the names are what the PKI is protecting, as well as communications between them.
Which is back to where we started, that DNSSEC was the right idea with the wrong solution, so we're stuck with a hack.
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.
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.
Regarding where the PKI "should" be, it's good to want things!