Ok, here are the average annual costs:
$1.53/th (incl distribution and transportation)
Last yr utility bill was $3,000.
The furnace will be installed on a finish basement. 3/4 of the ceiling have drop tiles that can be removed to work and it will be a run of approx 100'. Which does not strike me as impossible or too expensive.
Another thing that stroke me odd was that one of the contractors mentioned that my ductwork was design for 5 1/2 tons and I have a 3 1/2 ton AC unit. I also have one duct line servicing two floors.