Unless yours is one of the largest and crummiest houses built since 2000 in WA there's no freakin' way your heat load is anywhere near 95,000BTU/hr (with the windows & doors closed, anyway...
) The fact that it's not even being used for heating the domestic hot water is almost criminal. Many newer houses could be heated with the burner the size of what's in the hot water heater.
In western WA the
99% outside design temps are in the 20s F, and a typical heat load to floor area ratio of code-min new construction runs about 9-10BTU per hour per square foot of conditioned space (with many exceptions on both sides of that number to prove the rule.) In eastern WA (particularly at elevation) the design temps range from mid positive single digits well into the teens, and heat loads run in the 11-12 BTU/ft^2-hr. So if this house is a well insulated 8000-9000 mansion it might actually need a 95K boiler. The average house won't need more than a 50K boiler, and there are many smaller or better insulated houses where a 50K boiler would be oversized.
Sizing the boiler correctly for the heat load is something that can only happen at boiler-swap time, which is typically only once every 15-35 years. Right sizing it is important for comfort, efficiency, and reliability/longevity. So let's figure it out, OK?
Since you have a heating history on the place, with a ZIP code and a couple of wintertime gas bills with the EXACT meter-reading dates an fuel use it's pretty straightforward to estimate the actual heat load of the house based on how much fuel is used per heating degree day. The ZIP code is necessary to figure out a reasonable weather station to
pull data from at degreedays.net. For a "...house that is well-insulated..." it's better to use 60F as the heating degree-day base, but if it's a crummy enough house to need a 95K boiler base-65F would be more appropriate. With the fuel use & total accumulated HDD between meter readings, and the boiler's nameplate efficiency, the boiler becomes the measuring instrument. Only wintertime billing periods should be used, since that's when the solar gains and other uses of natural gas inject the smallest error in the measurement.
The short answer to the cost issue is "it depends", and one of those dependecies is the competence of the installer, and how the heating system is currently configured. At the very low end it might come in at about $8K USD, but depending on how screwed up the original system design was (and I'm assuming some level of incompetence here, based on boiler size), it could run as high as $15K or even $20K, depending on the complexity of what needs fixing, assuming you're installing a modulating condensing boiler.
How many zones?
How big is the house?