First bit of advice. Don't ask anyone at HD or Lowes for estimates, they tend to mislead people rather than help.
$20K seems extremely high, extremely. Get multiple quotes and investigate as much as you can about the contractors. Try to make sure they've been around your area for quite awhile. Ask for references and stay on top of them, I'm not saying to ride the contractor, just stay involved in the project. Don't go away for a week hoping it'll be done while your gone. Ask for copies of the permits and don't let yourself be bullied. There's alot of good contractors, unfortunately the bad ones can make them all look bad.