The way around this is for there to be fee SSL signing CAs that have their root trust certificate commonly installed. It is getting to the point now startssl's root key used for their free certificates is trusted by most browsers (http://en.wikipedia.org/wiki/StartCom), so you can probably use those for your needs. I don't think any other of the free providers (like cacert.org) have this level of acceptance yet.
The difference between using a free cert from startssl or similar and using a self-signed certificate is that startssl will only issue a certificate to someone who has somehow verified they are in control of the name being certified (i.e. their contact details are in the whois records or such - I'm not sure what validation method they use as I've not used their service yet myself but they must do something adequate enough to get their root cert trusted by the big name browsers/OSs), whereas I can self-sign a certificate for any domain name, as could you, as could that nefarious transparent proxy.
TL;DR: For personal use on your own machines, use a self signed cert and install your CA cert as trusted on your machines. For more general access (i.e. a public facing service) you'll have to try startssl or pay your dues (otherwise even "encryption only" does not work because of the proxy problem).