Too true. The old model is that you have to sneaker-net that first step. To get someone's public key, you'd literally meet them in person and they'd hand you a copy. We don't do that anymore.

I can imagine alternate approaches (service that stores personal keys on an HTTPS server signed via a public cert, keys in peer-to-peer filesharing with the checksum provided side-channel), but that gets increasingly more elaborate for diminishing return.