If there are no public keys pinned to clients (say secure messaging apps like Signal where each user generates their own keys), users need to check the public key fingerprints to make sure there's no MITM attack taking place.
So very likely unless Bob is comfortable with this situation he stills need a mechanism to find out who he's talking to. On the upside he does now have an encrypted channel on which to continue the work.
At scale that only practical answer is an Authority, a Trusted Third Party, people _so_ trustworthy that Alice, Bob and maybe even Mallory agree that they know who is who. In one sense this is so hard it might be impossible. But then again maybe it works anyway?
If you don't need scale, for example maybe you're a conspiracy of a few dozen people trying to bring down the Authority, then you have lots of other options depending on your circumstances including Out of Band verification and the Socialist Millionaires Protocol.
If you are a college kid and convinced that everybody on your Facebook friends list, and everybody on their Facebook friends lists, is a fundamentally good person - but that the Authority is a shadowy conspiracy against you all, you can use the Web of Trust, right up until the guy who once lived with a friend of your cousin's housemate steals your life savings and leaves you in a bathtub filled with ice with a hole where one kidney used to be.
I guess it doesn't protect against something attacking and snooping on your machine though.