There are certainly other options too: here's my suggestion-
The first time you go to a site where the certificate is one you haven't seen before, the browser should show a nice friendly page that doesn't make a fuss about how dangerous it is, and shows a fingerprint image for the site that you can verify elsewhere, either from a mail you've been sent, and with a list of images from fingerprint servers it knows about that contain a record for that site shown next to it.
Once you accept, it should store that certificate and allow you access to that site without making a big fuss or making it look like it's less secure than an unencrypted site. This should be a relatively normal flow and we should make the user experience accessible to normal people.
It's basically what we do for ssh connections to new hosts.