I'd think about using opto isolators between your relays and mc, Why relays? why not use a single chip H-bridge motor controller? Much quieter. DO your motors have rf supression caps installed?,
I used to work with micro controllers for a living, used many brushed motors on medical lab conveyor systems, never had any noise issues.
Far lower parts count using proper h bridges, use one that runs CMOS levels and you can control it right from the micro controller without any other parts. I have a few that will run 2 motors forwards and reverse independant of each other. so you would only need 3 bridges. Easy to find that will take a 3 amp load.
Sounds like you really need noise supression in your circuit, I'd try the caps on the motor first and see if that solves your rf problem. Then try isolating your motor driver circuit from the micro controller.
are you sure its rf causing your problems? You could be getting voltage spikes back from the relay, they do bounce a few times before they close for good. (I have a stock de-bounce snip of code I use for all mechanical switching circuits) I'd never run a relay from a mc without proper de-coupling.
Cheap brushed motors could be a problem, I have no idea what you are using but cheap motors usually seem to arc a lot and cause a ton of rf.
I can't remember the values right now but 2 small ceramic caps grounding the leads to the case and one electrolytic across the motor terminals would be a quick easy one to try. Use about a 25v electrolytic.
Then I'd try to lose the relays and associated antique technology and switch to a solid state motor controller.
Is this project on a board yet? You also want to be careful about how your traces run, keep motor stuff away from signal stuff, you can get weird capacitance issues between traces on a board, yes the board will act like a cap! If it's on a breadboard try moving the wires around and see if that helps.
What micro controller are you using? I was mostly using Pics, have done a bit with motorola though, I like Pic assembler much more though, simple RISC micro controllers. Hundreds of different varieties out there, 8 pin and up, I've used them to prototype many things because they are so simple to write code for.
Heard somewhere there is a PicBasic compiler, never seen it though. Assembler gives much smaller tighter code.