As Neil explains you most likely get a voltage dip when the motor starts. If you're using a transfomer/rectifier/ linear regulator setup, you need to ensure the regulator has enough 'headroom' (ie enough volts) to ensure regulation even with the voltage dip. I've rarely had this problem as I use switchmode supplies that can cope with a severe voltage dip - the ones I use are rated 90-260VAC and I'm running 240VAC. The voltage spike you see may be due to your measurement setup although you could be getting actual voltage spikes due to capacitive coupling via the transformer when the motor relay opens. I would suggest you put a snubber across the relay contacts - the values vary depending on the actual load, but since you're talking about a single phase motor and a relay as opposed to a contactor something like a 100R 2W resistor and a 100nF X2 rated capacitor in series placed across the relay contacts might help to tame the transients. It will also make the relay last longer. Don't think a solid state relay will make your problems go away!

Things to remember:
a 7805 reg needs at least 7V in to regulate.
put a diode across your relay coil.
motors pull over 10x their rated current on startup.
motors are inductive - when you open the circuit to them you get a transient. These transients being an inductive spike have very fast risetimes, therefore it doesn't take much capacitance to couple enough energy to cause problems.

To find out more about all of this, I suggest you read up on PLCs - the manufacturer's app notes have many recommendations on switching various types of loads. I would also suggest you look at other equipment to see how other designers have solved the problem - most washing machines have electronics these days, see how they do it.