I received two job offers, accepted and signed the first contract that came through (was worried either job might fall through considering my previous experience with rescinded verbal offers). Now I'm regretting that decision, the recruiter for the other role does not know I signed the contract, I told him that I need to think through both offers. How should I back out of the signed contract? Another problem- both recruiters know the companies involved.
Why does it matter that both recruiters know the companies involved?
To back out of a signed contract, you just say "I am backing out of a signed contract, sorry."
You don't need to tell them you are taking another offer, the offer you are taking, or any other details. The recruiter dealing with the contact that you are reneging will hate you, and will bad mouth you to everyone he or she can think of.
So whatever you do, do not tell them about the other contract, or the other company. If they call and are rude, just hang up. You owe them nothing.
You should check the contract (that you are reneging, but of course, check the other contract too!) for any odd pitfalls you might stumble into. Typically there isn't much anyone can do about you signing a contract then backing out (for workplace agreements). The notice period etc doesn't really matter as you are reneging on the entire contract.
They might try to scare you with a lawsuit (or, more likely, the threat of one) ~ I don't know where you are, but typically that kind of thing involves proving damages to the company in question. You are unlikely to have caused them any damages given you never started working there.
But to answer the unasked question "how can I make the recruiter/company that I am walking away from not totally hate me" - you cannot.