My point is that it doesn't have to be visibly complex. gmail or outlook could automatically generate and store a public key for every single account transparently then just append signatures to the bottom of emails while providing the public key directory for their users.

Then any random client can hit keys.gmail.com (or whatever pseudo standard one wants for finding the key servers) cache public keys and on some TTL check for revocation/etc.

Then the only thing the user would have to know about is whether the from box is "green" indicating that the user was validated, "yellow" indicating an invalidated email, or "red" indicating a problem with the validation. Once the validation is complete via a back/forth exchange the clients then know they can encrypt emails to the destination, thereby turning the from field green on the next email exchange.

Sure people using those services would also be allowing the service to see their private keys, but for phone apps, or desktop applications the key generation portion could be done on the machine and only the public key pushed to the email providers keyserver.

Plenty of other email services (proton mail, symantec) make this very easy for the end user.