That's usually fine for new servers, but what about old servers, e.g. if you're a dev who just joined the company? Most companies don't seem to have a secure way of seeding clients with the initial host keys. I've never seen it.
One way to do this is via SSHFP (ssh fingerprint) records in DNS. Unfortunately they do not seem to be particularly widely supported nor widely used.
A lot of people ignore the importance of this part. It is also a bootstrapping issue: At some point you need to get the key into known_hosts. Most people do this by confirming it the first time they connect. That's usually fine for new servers, but what about old servers, e.g. if you're a dev who just joined the company? Most companies don't seem to have a secure way of seeding clients with the initial host keys. I've never seen it.
We solve this with a script that gets them from Puppet (via PuppetDB, its repository of host "facts"). That script has to hard-code the host key of the Puppet host, of course.
Another solution is using the X.509-style certs to sign each host with your own CA, but I haven't looked into that workflow. Edit: It's actually a much nicer workflow. You can sign users, too.