Trying to understand how Digital Certificates and CA are indeed secure

Is the only protection here that Bob actually checks that the public key on the returned certificate matches what he originally sent in his request to the CA?

If the public key was switched before the CA used it to create the certificate, then Bob's web site won't work at all. The private key, which he has kept safe, will only work with his original public key. It is unlikely the attacker can MITM all connections and prevent this fact from becoming obvious.

intercepts Alice's request to veriSign when she asks for veriSign's public key, and switches it out again with the matching public key to the malicious secret key.

Alice doesn't reach out to Verisign; Alice only trusts copies of the CA certificates in her browser or computer's trusted certificate store, of which Verisign's happens to be one.

The trusted certificate store is populated at install time (of the OS, or in the case of Firefox, of the application) and is then updated via regular OS or Application updates as necessary - less than you'd think, as many root CAs are long-lived.

Good question. The certificates of the most trusted CAs are normally included into software install package, e.g. into browser installer, into OS installer, or are preinstalled on device like smartphone. That's why the browser (or some other application) will notice if certificate is really from the specified CA.