My $0.02
First, get a second opinion on the furnace. Don’t say a word about what you were told by the other company just tell them that you’re having issues.
Second, I’d definitely look into replacing your AC unit simultaneously if it makes sense. You’re far more likely to do it now at a cheaper rate once you have them there then calling them back in 2 years if it’s on its last legs or is a comparable age.
If you happen to be living in the Hastings, Red Wing, Lake City area shoot me a PM and I have a perfect recommendation for you. If not, I am not much help with recommendations.