The Custodian's point about fan size vs. speed is one I've often thought of, but being also of the
cheap bastard bent, and having extremely limited tools and time, I've yet to
experiment with anything larger than an 80mm case fan as a relpacement for the CPU fan. However, a few things that've worked well for me:
My fileserver doesn't do much other than sit and dish out NFS and NIS data. And since I keep it running 24/7, the noise was audible while watching TV, and other non-computer-related activities (such as... watching TV). So, I decided that the annoyingly loud CPU cooling fan really wasn't justified. So I replaced the heat-sink with a copper one (a Cooler Master one), removed the fan, dropped the clock multiplier to a mere 2x (bringing the clock speed down from 333 to 133MHz), and dropped the core voltage to the lowest (2v) that the motherboard would support. And also made damn sure that the OS was configured to make HALT calls when in the idle loop, and avoided running anything too CPU-intensive on it at all. Nice and quiet. NB. Don't try this at home, kids. And if you do, and your machine overheats, don't say I didn't warn you...
For my workstation machine, which really needs its fans, a different approach was needed. First, a good-quality CPU heat-sink (same copper one as the server), but run from the 5v line instead of the 12v line. It keeps the air circulating at a reasonable rate, but is a lot quieter than normal. The GPU and PSU fans are harder to slow down, but at least they're not as noisy.
The most noticable reduction in audible noise came from where I placed the machine. Out in the open, is still made a racket, but strategically placed underneath my desk and behind it's vertical board, (with access to drives from the side of the desk), it was a lot quieter; particularly since the rear fan exhaust no longer pointed at a reflective wall, but at a bunch of cardboard boxes and manilla folders under the desk which acted as baffles. It's tempting to get some soundproofing foam to line the inner surfaces of my desk too.
I can't help but wonder, though, what the ideal solution is. I almost care enough to calculate how large a surface area of heat sink would be required to maintain a typical PC at operating temperature with convection alone. Nonetheless it surprises me that PC cases don't come with corrugated side panels.
Quieter active cooling systems seem like a good option too, though more expensive. A fan is just the simplest way of keeping things cooler than convection alone, it's not necessarily the best. The most obvious ones are liquid cooling systems, with nice, large radiators and quiet pump motors, but they're risky since spills or leaks could severely damage your kit.
There comes a point, though, when the amount of cash spent cooling a PC machine could be better spent on an alternative, less power-hungry machine; the sadly discontinued G4 cube, or a thin client (plus a server hidden in the closet), but the problem with these is, of course... they suck for games.