Check the three links below. They'll help.
As far as BTU inputs go you need to understand that the vast majority of furnaces range from oversized to grossly oversized. I don't know what the proper size would be for your house. Only a properly done Manual J can determine that. But at the same time it's very likely that any of the three furnaces you mentioned would probably heat the house just fine. The design condition for my area is 27 degrees. That means that a properly sized furnace must be able to maintain 72 degrees indoors when it's 27 degrees outdoors. If the furnace was truly properly sized then it would literally run 100% of the time when it's below 27 degrees. We get 27 degree weather a dozen times per year. I doubt that my furnace runs even 50% of the time. The 80K BTU furnace would run longer than the others. But that's a good thing for many reasons. Ultimately a Manual J calculation should determine the size.
80% vs. 90% is as much personal preference as it is anything else. The 90 saves on gas. The 80 saves on upfront costs and potential maintenance and repair issues that may occur on the 90. The 90 uses sealed combustion and is quieter.
I wouldn't buy an AC without a TXV. They're cheap and VERY beneficial to system operation. TXVs actively modulate the flow of Freon to the cooling coil. Without one the system just feeds Freon at a fairly fixed rate despite changes in the heat load.
There's no clear choice at this time. Both R-22 and R-410A have their pros and cons. Don't let the 410A zealots fool you. R-22 will be made until 2020. And even after that it'll be readily available. If and when you find a contractor that's head and shoulders above the rest, go with his recommendation.