No appreciable delay needed. Once powered up (<100mS) the PIC should take only a few mS at most to initialise. Its first task then should be to switch on the relay. So from pressing the button to the relay pulling in is just the blink of an eye.
It funny I was just woundering how long it takes a micro to do a cold start. Is "mS" micro sec or milli sec?