Basically, your cert needs to be signed by a cert authority that the other person already trusts. As you’ve found, nobody really wants to deal with this for individuals.
Generally, what people do is create a self-signed cert and publish it, either on their own site or that of a third party like https://keys.openpgp.org/, then convince people to trust it, usually through an existing trusted communication channel, such as by meeting in person.
Certs and keys are more or less the same thing, a cert just has metadata like being signed by a CA, while keys are solely the public-private keypair and nothing else.
Even with a cert signed by a trusted CA, most people are not going to go through the effort to figure out how to send encrypted mail, assuming their client even supports it!
The only place I’ve seen it successfully implemented is government, where software and certificates are highly standardized, and being unable to send encrypted email is not an option. Your average person barely knows how to use Outlook.