Your public key can be 'signed' by any other private key you like. However, your recipient's issue will be how to trust the signer i.e. the burden of trusting your public key's origin has now shifted to the burden of trusting the signer's public key origin so not much have changed.
A 'CA' is a vague term. If you mean a SSL chain CA (as in browsers certification authority) then various CA's have their public key hard coded into the browser on installation and this removes the need to verify the signer's public key with a third party. PGP and similar encryption schemes don't work like this for a host of reasons but mostly because signing individual keys would be prohibitively complex and restrictive (think how complex/long the process is to have a signed SSL cert for a website for example, now multiply this with all of the PGP certs out there!)
PGP cert trusting working on a web of trust i.e. the recipient needs to have some 'trusted' public keys pre installed on their keychain that have been marked as trusted by them usually by some side channel (phone someone up and check the key fingerprint for example). If your recipient does not have a trusted public key for someone you are using to sign your public key then they need to check the key with you by some other channel e.g. calling you and asking you to identify it by fingerprint etc. or to download it from a trusted third party keystore where the keystore has a verification mechanism.
So, get your public key signed by as many trusted keyholders as you can and hope your recipient has a trusted corresponding signed public key, or call them for the first key install into their keyring and confirm the fingerprint. Once installed and trusted on their keyring you are good to go without further trust issues.