Trust on first use combined with preloaded public key lists is the best of both worlds in my opinion. You may say that browsers made in authoritarian countries would sabotage the preload lists, but they could also bundle illegitimate CAs or break HTTPS in other ways anyway.
This. Some standards bodies (arguably) made a big deal about client certificates some time ago to reliably pin client identities for client->server connections (whether it worked is a different story), and I certainly think having functionality for the reverse (pinning server identities) should exist too.
Doesn't have to be Gemini even, but I think getting buy in from browser vendors after the removal of HPKP is going to be a problem...
Another option would be something similar to Go's sum database, but with something like a DHT instead of a hosted centralized service.
Or perhaps instead of a DHT, users could export all their certs to a file and combine/compare entries in a grassroots manner with each other and with devices on different networks.
