StartCom is a good CA for S/MIME. You need to create an account, verify your email address, then create a certificate for S/MIME email. Key generation looks like it happens on their side, but it actually occurs in the browser using the tag.
Once the certificate and key are in OS X Keychain, export it into a p12 file, use a good passphrase, and email it to yourself. Then open it up on the iOS device and install the certificate.
You'll also need to install the StartCom Class 1 Intermediate Client CA certificate. Open this link in Mobile Safari:
https://www.startssl.com/certs/sub.class1.client.ca.crt
(That certificate is in turn signed by the StartCom root CA, and as far as I know that's already trusted by iOS. There should be no need to explicitly trust any certificate. If necessary, the root certificate is here: https://www.startssl.com/certs/ca.crt)
Now go into Settings, tap your account, tap Account, tap Advanced, and enable S/MIME at the bottom. Enable both Sign and Encrypt, and pick the certificate/key pair you previously installed.
At this point you can send signed emails, but they won't be encrypted, not even messages you send to yourself. It should say "Not Encrypted" under the "New Message" header when you compose an email.
Send an email to yourself. Open the message, tap the Sender (there should be a little check box), and tap View Certificate. The certificate will be displayed along with "Trusted". Tap Install to install the certificate.
At this point, your own certificate should be associated with your email address, and you can send an encrypted message to yourself. Test it by composing a new email to yourself. A lock should appear next to your name after you have entered the email address.
To install someone else's certificate, have them send a signed (not necessarily encrypted) message to you, then tap the sender again, View Certificate, Install.