I suggest an inrush current limiter. It is effectively a resistor that lowers it's resistance to near zero after a few seconds. This would stop a large current draw, and slow the startup of the fans. Online suppliers like Digi-Key usually stock them (
http://www.digikey.com/?curr=USD). You will need to decide the initial resistance, and total energy that the device absorbs before going to low impedance.
First let me say I don't have a clue about inrush current limiting.
But if It adds resistance to slow the start of the fan, wouldn't also be drawing significant power too?
It is actually an NTC thermistor, which is a device that lowers its resistance when heated. When cold (room temperature) is may be say 10 ohms. When the fan relay kicks on, the thermistor will initially allow only about 1.4 amps to the fan. As it heats up from resistance, it's resistance will lower to something like .1 ohm, which is enough to keep it warm and pass 15+ amps continuously. Sorry for the techno-talk, but I'm sure you can understand it.
This one might work well. I don't know the running state current of your fans, but this one is rated at 15 amps.
http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=570-1058-NDWhen on, it will use about 12 watts of power and will have about a 1 volt drop. It will get somewhat hot when running, so don't let it touch anything.