The solution I use also involves different style sheets for different browsers. I use relative font sizes (ems) for everything but IE3/Mac and Netscape 4, and I don't mess with font sizes at all on those two browsers, so the fonts are no worse than in a non-CSS browser-- about the best you can ask for under those circumstances.
This seems to work OK in the browsers I've tested. The major browser that doesn't support ems correctly is Netscape 4, and so many other things are broken there that it's not worthwhile being very ambitious. (I'm not a commercial Web designer, so I can get away with this.)
I make the distinction using the old @import hack, which is a blunt instrument and probably considered mortally passe these days, but has the advantage of being easy.