Do you want this done with relays, or can we use electronics?
One "non-electronic" solution is to have a resistor in series with the relay coil (with a low enough resistance that the relay can still operate) and a large capacitor across the relay coil. That will delay the turn-on of the relay after power is applied. The relay should be able to switch 500mA.