It's not really all that hard to do your own. Heating and cooling loads aren't a function of the square footage of the home- it's a function of the construction R-values and window U-values, and the orientation of the house relative to the sun etc. The old schooler rules of thumb don't leave you too hot or too cold, but more often that not that approach will oversize the equipment by a large factor- 2x oversizing is typical, 3x oversizing common.
A pretty-good heat loss freebie is downloadable here:
http://www.taco-hvac.com/products.html?current_category=370 The instruction vidi lives here:
http://www.taco-hvac.com/products.html?current_category=370&show_vid=1 $350 isn't an outrageous amount to ask, since it involves a lot of measuring and poking around to get it right- time is money. I've known some HVAC ciontractors who would take the Manual-J off the installation price if you opted to let them install it, but not all. Most would just have it as a line-item in the total bill, or billed separately. If YOU take the time to measure everything and enter it into the Taco tool, play around with the infiltration factor and design temperature numbers a bit so you know it's not too wrong you'll probably hit pretty close. I haven't vetted this tool against others (just downloaded it myself), but it has the look & feel of some of the decent tools.
Don't be surprised if it comes up with numbers significantly smaller than the ratings of your existing heat pump, and try to trust the tool when that happens. If your old system was 4 tons, and the tool says 2.5, go with 2.5 (3 at the most.) Most of these tools have some amount of oversizing factor built-in, and if it's saying 2.5, it could easily be closer to 2. Going with multi-stage or variable speed scroll compressor heat pumps (and variable/multi-speed air handlers) you can get away with some amount of oversizing without losing efficiency, but with single-speed versions (or more than 2x oversizing) you'll take a hit in both comfort as well as efficiency. In that situation a variable-output 2.5-3 ton will run long, efficient duty cycles, and will be quieter and more comfortable.
Like jonr says, you could use the ratings of your old system as an absolute upper-bound assuming it kept up even on the hottest/coldest days, but think multi-speed/variable-speed if you want to max out on comfort.