Heat pump is not a good choice in your area unless it was maybe a geothermal one. A regular air heat pump won't work at -20 and you end up using the electric heater ($$$).

The guy that says he will do a load calculation, did he take any measurements? If not, he probably won't do a load calculation unless you choose him, even then you need to put it in writing. Ask the other guys if they will do a load calculation.

From what you said, you seem to have a leaky house and leaky ducts that are also undersized. Maybe try budgeting for them to fix your ducts at least. Wouldn't make sense to put in a brand new AC and have all that cold air warm up before it gets to your room. I would almost recommend putting wall furnaces and window AC system... you might get more comfort from those if fixing the ducts will be out of your price range.