I'm suprised that you need a 110k BTU furnace in a location where you need 3.5 tons of cooling. You'd need to be well north for that match.
+1 on 95%+
I'm partial to Carrier Equipment, but you need to have hte Performance series quoted. I also think you should alwasy price, good better and best. I'd alos price out a York Affinity modulating furnace and a Carrier Infinity both with 2 stage AC.
York is the major brand that we sell, so i'm probably biased. The TM9V is a really good furnace and I love the LX series of AC and heat pumps, much more than the York affinity. It is cheaper and I believe it's a better system. You can match the 14.5 Seer outdoor unit with variable speed motor and txv to achieve almost 16 Seer. I think with the 3 ton it will match to 16 Seer and the others are 15.6+. We have installed many like this and have had no problems... knock on wood