Respectfully disagree about star probes - they can be better, but that depends on your probing system. Analog probes, yes, but you aren't going to get into analog probes at your price point. The problem with star clusters and touch trigger probes is that most touch trigger probes (TTP) don't register hits on -Z surfaces, the hit is recorded by the deflection off center in the ±X/Y direction. The most common probe type is probably the Renishaw TP20, and while you can get what's called a 6-way module, the performance is.... well, we did some testing before and were less than impressed. Our customer couldn't justify the extra cost of those modules for the minuscule difference in accuracy. The other downside is building the cluster - it takes a while and once you get it set you don't want to tear it down. This will necessitate needing multiple modules and probably a probe changer (modules approx $600-1k each, probe changer $6.5K). Another problem with stars and TTP is the added weight, you have to make sure you get the correct modules for the build. If you're using a TP20 and a long build, you need to get an extended force module, which I completely despise and refuse to work with on automatic (DCC) machines.
The automatic probe heads have a stated 2 sigma positional accuracy of 0.5 (with a 20mm stylus, IIRC, it may be a 10). And I can say this with certainty - of the people I know who were considering an automatic head but opted for a manual, all regretted that decision. If you do decide to go that way, though, with the idea of upgrading down the road, have the machine pre-wired for it (you have to specify that when you order it). It will add a couple K at the outset, and save you at least twice that down the road. Also, don't try to get a PH9 because the price is good, those have been obsolete for nearly 10 years now and Renishaw is not supporting them. Repair is a PITA.
OEM refurbished prices are about 80% of new, for that you should be getting a machine that's been checked (at least should have been), with a warranty, and current software/firmware. You can check with a reputable 3rd party source. If you decide to go the auction or machinery clearing house route, budget in another 25-50% for repairs/retrofits.