I disagree with your evaluation, Tannin.
KDE is pretty good, actually. It has problems but dismissing it as something that is equivalent to Windows 3.1 is entirely incorrect.
You have to understand that there has never been any uniformity to *nix desktops, only in the "Presentation Layer" commonality of using X. Several companies built their own widgets, and at various times there have been attempts to make more standard desktops - CDE (common to HP, IBM and Sun, at least, but it wasn't free, so never dripped down to free 'nixes, and I don't think SGI ever adopted it) is the best example, but none have gotten very far.
Now, in the world there are really only four big Unix vendors left. Sun, which has dropped CDE in favor of the slightly less-sophisticated GNOME desktop for its Solaris OS. HP, which is transitioning from PA-Risc/HPUX to IA64/Linux, SGI - going Linux, and IBM, whose Linux initiatives stretch across all the platforms it makes... and Linux is fast becoming a replacement, or at the very least a baseline for their Unix systems.
KDE (and, for that matter GNOME) may not be as clean as CDE, but they both far outstrip mwm, OpenWin, NeWS - all the other contenders for a standard UNIX (tm) desktop. The level of sophistication is higher than you think, too. Probably between Windows 95 and Windows 98 - not forgetting that Microsoft would undoubtedly sue the pants off anyone trying to borrow too much from their GUIs, that's not a bad deal at all. Both are also a lot more user configurable than any other GUI I've ever seen.
I know. Fonts are a main issue. The thing is, real UNIX boxes all use some licensed system or another (eg Solaris uses display postscript)... so the free Unix systems have had a real challenge in that direction. No one developed a free font system; all the font technologies as well as the fonts themselves, were licensed and unavailable for redistribution (this was also a major factor in keeping free 'nix GUIs primative. The best graphics libraries couldn't be afforded). Ouch. I don't know how truetype was finally brought in, but I imagine the ubiquity of Windows machines helped in that regard. Now, the problem is the there is a great deal of legacy material out there that does not support truetype, which I believe is the font-related problem that you experienced. This will change. Things have gotten progressively better with every passing release of a major 'nix, and they will continue to get better.
I wouldn't expect a GUI for 'nix to ever be out-and-out better than the ones from Microsoft. I would expect that the GUIs for 'nix ultimately will be more than good enough, even for you.