If you want it done right, get Malcolm or KC to do it. I wouldn't risk such a big job with anyone else.
Binding makes it a little harder, thus more expensive. Expect to pay around $300ish for the job... possibly more.
Out of curiosity, why are you considering a refret in the first place? Did some guitar shop tell you to do that?