LC lowpass filter optimization
I run into this problem regularly and fix it by adding a capacitor across the fan power terminals with series inductor to the incoming power.  Depending on the power requirements of the fan(s), I'll use an inductor that ranges in value from about 330uH on up to 1200uH.  The capacitor I use is a 100uF 35V AX or GX family part from Sanyo - we stock these capacitors for use in our SMPS power supplies and they work very well.

Ferrite-core inductors seem to work well.  The large inductors use Renco RB-4 or RB-5 cores wound with wire that ranges in size from 12 AWG on through 18 AWG.  This is for load currents in the range of 5A through 15A.

Smaller fans use a little ferrite bobbin-core inductor at 1200uH.  The DC resistance is a little high on these inductors but for small fans, it's not a problem.

I've never tried to optimize the capacitor size or type.  Basically, the first time I ran into this problem, I tried using the Sanyo very-low-ESR capacitors that we use in other products.  It worked very well - and that was that.