[simfoo]

But then how does Alice know if she's talking to the right Bob and not some evil middle-man? In other words, she has to trust the server that it is giving her the correct public key.

[a1a]

Signing. I.e. Bob encrypts a dummy message or whatever with his private key.