I don't think xmag is a good test. I like my fonts but they still look bad in xmag.
In KDE what happens if you go Control Centre -> Appearance -> Fonts and look in the menus? Are the MS TT fonts there (Andale, Arial etc)? If not I'm mystified, if you've used the installer.
Then I have antialiasing and subpixel hinting on (same menu). I think most of my menus are Nimbus. Then you have to set the fonts in the individual apps.
The basis for all this (I'm guessing) is the XFree86 Font Renderer, version 0.4, according to /var/log/XFree86.0.log. 'Cos I've got no font servers or anything like that running.
Again, I don't know if this is relevant, but I'm running XFree 4.3.0 (HD install of Knoppix CD).
In fact I'm probably at least as much in the dark as you, but lucked out on this one. Try www.kde.org
PS: a better test is to enlarge the fonts in Konqueror (Shift/Scrollwheel) or use the menus. Letter sizes here go up to nearly 1cm and still look smooth.