It's not hard to generate a certificate request. While Firefox and IE may use different routines to do a local key generation, it's certainly not difficult.

The scary warnings you're talking about come up if you're connecting to an "untrusted" site - who's SSL server certificate isn't signed by a known, trusted root CA.

It's certainly the best solution to this problem.