About a year ago, I replaced one of my central air units for a bit more than that and there was minimal duct work required. It really depends on where you live, unit efficiency, size, etc.
Based on my own research, I'd highly recommend springing for a 2-stage over a 1-stage system. The variable speed systems are definitely comfortable, but will likely cost more in the long run. They're a lot more complicated and more likely to have issues and a lot of those costs likely won't be covered under warranty.
Double check with your electric/gas companies on rebates and be sure to include the costs with your
tax return.
Always get multiple bids for HVAC work. Sometimes they get busy and give you the "I don't really want to do this job" price. Even the good ones.