Obviously, I'm going to be burning bridges with Company A if I decline
to work there at this point, so I'm looking for pointers on how to
best handle such case. Should I notify them immediately or after
signing a written contract with Company B?
Before you notify Company A, make sure of two things first.
- Make sure you have a formal, written offer from Company B that you are sure you want to accept as is. If you need to continue negotiating, or if this offer might fall through, then don't notify Company A yet.
- Make sure there isn't some other Company C,D, or E that is ready to give you an offer that you want. You don't want to stiff more than one company if you don't have to.
Your best bet is to be honest with Company A and explain why you have changed your mind. I'm sure they won't be happy about it, but these things happen. If you are prompt, polite, and professional they will understand. Don't delay any longer than necessary, so as to minimize the damage.
I once worked for a company that hired a software engineer. He was due to start in a month, and waited until his expected start date to tell the company that he changed his mind and wasn't going to show up. There's no way anyone who worked there at the time would ever want to work with him in the future.
On the other hand, I've had several people over the years change their mind within a week or so after accepting my offer. I wasn't happy, but I understand that these things happen.
Are there any legal repercussions on declining to work with Company A?
That depends on your contract, and local laws.
In most US locales, in most contexts, there will be no legal repercussions, although as you indicated there will be a hit to your professional reputation and you will clearly be burning bridges at Company A and with anyone there who knows what you did.