You'll probably need to add a double breaker for each heat pump. Check your box to see if there is room. If not, the service box will have to be upgraded. That costs about $3500.
Heat pumps and gas furnaces are about on par these days. If you can move your house to all-electric, it might be cheaper because you can do away with the service charges on your gas bill. Also note that gas pipes eventually need replacement too, because they rust out and the putty on the threads eventually turns to dust. If your gas plumbing is >50 years old, think very hard about any plan that involves using them for the next 20 years or so.
Your brush with death by carbon monoxide is a reminder of the dangers with natgas. As
more research indicates the health risks of unvented gas appliances in homes, it's worth considering switching.
I spent $4300 recently to upgrade my panel and have electrical lines installed for the stove, dryer, and water heater. Thus as these appliances wear out I'm replacing them with electric. Also, my house's gas pipes are 80 years old, so abandoning them at some future time will save a big plumbing bill.
WRT replacing your existing HVAC units, it would probably be cheaper if you could find a way to use one bigger unit to heat and cool the entire house, rather than 2. In a 2-story house, this might involve routing ductwork between the two stories, for example by running a duct from the craw space up to the attic through closets, the attic of an attached garage, or new enclosed spaces such as a little box in the corner of a room. Set up a valve so you can direct more air to the upstairs versus downstairs vents in summer or winter, respectively.
