Sounds like a power supply issue, romans advice sounds a logical one, you dont necessarily have to put the 7805 on the same board, though it might reduce your problem.
Does the relay have a back emf diode?
And if your swtching fans or fridge compressor motors then your load is inductive and will cause flash at the relay contacts, I've had this screw up pics before and the longer the leads are the more susceptible it becomes.
A 100nf xrated cap and a 1w 100r resistor across the relay contacts will lessen flash considerably for this sort of load.
This combined with power supply filtering 100uF cap and 100nF cap at the pic should improve things, I've prototyped pic software on breadboard a few times and the only way the chip would even boot is with a 100nF right accross the pic with the a/d converter enabled, with the a/d is disabled the cap isnt needed, I never worked out why this happens.