We had our entire system replaced about two years ago now. Was around 17k with furnace AND heatpump. I had maybe a half dozen quotes and picked the one that was just above middle of the pack (mind you we had to have it replaced as the system was failing).
We still have oil as backup for really cold days.
I was curious if this was all worth it so have been tracking our electricity and oil spend. We'll break even easily within the next few years compared to if we had just replaced everything with the cheaper stuff (non heatpump). Granted we were oil only for heat so that may not be a fair comparison for where you're at but for us its been a no-brainer.
We did have one quote just over 20k for basically the top of the line system which we were told would have given us more savings and a more comfortable home. I do sometimes wish we went with that (payback would have added some years).