Well, you've already found the-mother-of-all-Linux-fonts-threads.
One radical solution is to try a completely different approach--boosting your resolution and using larger fonts. If you're using a CRT monitor, you can get 2048x1536i@85hz resolution (for video cards which support interlacing--NOT nvidia). It looks AWESOME, far better than Windows ever did (it's hard/impossible to configure Windows applications to use large fonts well).
Once you get used to crisp detailed look of 2048x1536, it's hard to go back. In particular, finely detailed serif fonts like Garamond or URW Palladio look wonderful at 2048x1536.
Even my old 333mhz P2 Celeron is running at 2048x1536 on an old 17inch CRT monitor. This monitor is so old, it can't officially handle anything higher than 1280x1024. The old Ati Rage128 video card it uses officially can't handle any resolution higher than 1600x1200 either--but interlacing literally halves the bandwidth requirements. I merely entered in the same 2048x1536i@85hz modeline I use on my other machines, and it worked! To maximize performance, I don't even use anti-aliasing on that machine, and the fonts STILL look far better than any Windows box.