ssh is started before hostkey is installed/regenerated

This can be easily reproduced on UEC instances (where you tend to know the IP in advance and can start trying to ssh in as soon as the vm is "running" :)

Changing this to "Confirmed" since I see this behavior occasionally on EC2 when I ssh in too quickly and then get a host key changed error when I ssh in again later.

The solution I'm going to implement is to remove ssh keys from the image, so there will be no "built-in hostkeys".
In testing, the ssh server will then still start, but attempts to ssh to it will fail:

$ sudo rm /etc/ssh/ssh_host_rsa_key*
$ sudo stop ssh
$ sudo start ssh
$ ssh localhost; echo $?
Read from socket failed: Connection reset by peer
255
$ sudo ssh-keygen -f /etc/ssh/ssh_host_rsa_key -t rsa -N "";
Generating public/private rsa key pair.
...
$ ssh localhost
The authenticity of host 'localhost (127.0.0.1)' can't be established.
RSA key fingerprint is 32:44:17:eb:21:5d:a1:d3:e9:c0:57:f9:1e:e3:ce:a8.
Are you sure you want to continue connecting (yes/no)?
...

I think this is good enough, it means that the window is still present, but
a.) in the window there will be no ssh keys reported by 'ssh' or 'ssh-keyscan'
b.) ssh host /bin/true
  will exit with non-zero
c.) when keys are available, ssh server picks them up.

just to point out here, Its a goal for ec2-init to be running early enough that it could actually block the start of ssh until the keys are generated.

This should not occur with latest images. There are no keys in the images.
If you try to connect before they're generated, you should get something like:
$ ssh localhost; echo $?
Read from socket failed: Connection reset by peer
255