Putting a small capacitor and/or a varistor(both appropriate rated) across the relay contact (not the coil) might help.
The capacitor needs to be rated for AC use to a voltage at least as high as your mains voltage. Also it should have a resistor in series with it. This arrangement is called a snubber. It can be connected either across the relay contacts or across the fan. It’s hard to suggest values without knowing more about the fan, but for 230V mains, 0.1uF in series with 100 ohms might be a good place to start. For 110V mains I would double the capacitor value and halve the resistor.