The chimney is shared with my hot water tank. Would they need to sleeve the chimney with PVC? Is that easy? Would hot water tank need to be changed at the same time to mid or high efficiency? Most of my basement is fully finished, so routing the exhaust is a concern.
At a minimum the water heater venting with a narrowing liner would need to be changed to avoid destructive condensation inside the chimney, but you may run into code problems sharing the chimney as a flue chase for PVC venting + combustion AND a metal low-efficiency combustion appliance liner.
It might be better to just swap out the water heater for a heat pump (electric) water heater, which needs no flue, and would allow you to seal up the chimney for less 24/365 stack effect induced infiltration.
BTW: Rather than just replacing an oversized low efficiency furnace for a high efficiency version with the same capacity is almost always a mistake. The vast majority of furnaces are sub-optimally oversized for their loads, and operate at too low a duty cycle to provide real comfort. You don't really need to cover the theoretical heat load when it's -100C outside, after all. The
99% outside design temps in most of Manitoba are ~ -25C or warmer, and if -24C was your design temp a furnace with no more capacity than the load at -40C would cover even the most severe cold snaps. Going with more capacity than 1.4x the load at the local 99% outside design temp results in LESS comfort rather than more. At 1.4x oversizing the furnace is running (1/1.4=) 71% of the time at design condition. At the commonly found 3x oversizing it's only running 33" of the time at design condition, and off the other 67% of the time. From a comfort point of view it's akin the difference between taking a 5 minute 2gpm shower vs dumping 10 gallons of hot water on your head.
To figure out what your actual design load is, use the old furnace as the measuring instrument by logging fuel use against wintertime heating degree-day data,
as outlined here.