I understand that the validity of any OpenPGP certificate is based on that certificate being verified by a trusted party within a web of trust.
However, for most people who don't use GnuPG every day, they will simply get their keys from keyserver.ubuntu.com once, and trust that they are accurate. E.g. when following the "how to verify" guide on Ubuntu.com:
gpg --keyserver hkp://keyserver.ubuntu.com --recv-keys "8439 38DF 228D 22F7 B374 2BC0 D94A A3F0 EFE2 1092" "C598 6B4F 1257 FFA8 6632 CBA7 4618 1433 FBB7 5451"
Although this communication will happen over plain unencrypted HTTP, I believe that the certificate we get back from keyserver will be signed by the keyserver itself, and so as long as we knew a trusted certificate for the keyserver we could trust the response.
But how, based on only running this command once, can we trust the keyserver, as I don't believe GnuPG will have created a trustdb file yet? Does GnuPG have a built-in list of certificates that it trusts which includes that of keyserver.ubuntu.com? If so, how can I find this list to check that this is the case?
In the absence of this trusted list, wouldn't it be possible for all my communications to be intercepted by the same man-in-the-middle (MITM), who could then be feeding me a fake certificate from keyserver.ubuntu.com at the same time as feeding me a forged signed package (e.g. the operating system ISO itself)?
The parameter for receiving keys is the full fingerprint of two keys:
The fingerprint is calculated from the public key (I discussed OpenPGP key IDs on Super User, if you want more reference). GnuPG will realize that the wrong key was returned, if the calculated fingerprint of the received key does not match the fingerprint that was requested. With other words: you may not trust key servers (they're operated by random individuals, which might well have malicious objectives), but you don't have to, all information received from key servers must be validated anyway. The range of possible fingerprints is very, very large: it is not feasible to find a collision (the same fingerprint for another key), even if you have vast computing powers like agencies as for example the NSA might have). Do not trust short key IDs, though.
For the same reason, you may not trust a key server's results when searching for mail addressees or user IDs. Not only could key server operators return malicious information, but key servers also do not verify anything at all (everybody could upload keys for arbitrary mail addresses). You always have to validate keys on your own. There is nothing like keys trusted by default in GnuPG, not even the keys of the GnuPG maintainer. If you trust the source listing the Ubuntu key's fingerprints, you could sign them to make GnuPG aware you verified those keys.
There also is HKPS (HKP over HTTPs), but this does not change anything considering the missing verification of key server information; HKPS has only been introduced so a man in the middle cannot record what keys you retrieve from key servers.