"The first time you log onto a server you get a signature"
Which is no more than a self-signed certificate. You can still play MitM. In a sound SSH implementation you don't rely on the key the server presents you on first access.
You're right with CAs - they cannot be simple commercial entities just selling certificates for profit. They should be bound to much higher standards and liable for their mistakes. Just, it will make certificates more expensive, and people instead want stuff for free.