It's difficult to advise without knowing in more detail what components you have or can obtain and your skill level. I'd be inclined to go with a simple delay circuit. A 10K resistor and capacitor (I'm guessing say 220/470 uF) would receive low DC power at the same time as you switch on the mains powered fan. A 1k resistor from their junction to the base of an NPN transistor would quickly fade up your LEDs a few seconds after the fan starts. Tried it on a breadboard and works, but further trial/error needed on the component values.
Have to go out now but can respond in the morning to queries, and draw a corresponding circuit if you need it.