I think (or at least hope) that you're misunderstanding the headhunter fees. I'm not aware of any case where a headhunter will charge the candidate a fee, if you run into one who does that's a massive black flag and I'd avoid them like the plague.
While their commissions are generally based off of the candidate's starting salary, that's a fee paid by the company to the headhunter, and assuming no one's being shady, it will never come out of the salary itself. The way it's meant to work is that the commission is supposed to act as an incentive for the headhunter to negotiate for a higher starting salary for the candidate, and for the position to be filled faster for the hiring company. Of course, YMMV with how this applies in practice, as it depends on all of the parties involved.
The rest of your advice is solid! I just wanted to vouch for headhunters since I've had good experiences.