We just had a similar situation and went with an all electric heat pump setup to replace both our oil furnace and AC. Looking into all of the options electric is less expensive than oil (and will probably stay that way for a while). We LOVE the heat pump and are saving more than $1k a year with it vs what we were spending on heating/cooling before.
The whole thing (including the backup electric coils for super cold days and the heat pump with removal of the old stuff and installation of the new) was $5k-something. But, we got quotes for other companies for the same work of in the $7ks, so super glad we got multiple quotes.
My understanding is that the cost of natural gas is less than going all electric, so you probably would want to get a new gas furnace vs the electric backup coils we got. However, I would look into using a heat pump with the new gas furnace. The heat pump will help a ton with the furnace's efficiency, as well as act as your ac (so you'd basically get it to use as your ac, but it could also be used with the furnace to improve efficiency).
I would recommend contacting several companies, getting quotes from each for (a) new gas furnace and ac, (b) new gas furnace and heat pump, and compare it all, taking into account projected savings for increased efficiency of heat pump. I would guess that getting one company to do it all will work the best, but get quotes from several.