Put the decision to participate in the hands of the community
Some sites have asked to be excluded from the HNQ. Giving sites the choice to put themselves onto the existing blacklist might be useful, and would involve the community that has to shoulder most of the negative side effects into the decision.
Give the community a way to experiment with the exact formula
This might not be possible with a reasonable amount of effort, but it would be very interesting to have the ability to simulate alternative HNQ formulas. It would probably have to be based on a snapshot of data because it's expensive, but even that could help to find better ways to select HNQ.
Allow users to collapse the HNQ sidebar
Currently users don't have a choice whether they see the HNQ or not. Give them a choice, and there are fewer reasons to complain about inappropriate titles. If you don't want to see the HNQ, simply switch them off.
Limit the self-reinforcing aspect of the formula
A question with a lot of activity has a better chance to get into the HNQ. A question in the HNQ list often gets drastically more activity and votes than without it. Maybe only counting votes from users that have contributions on the site could help.
Normalize between the sites better
Some sites are clearly overrepresented in the list. Normalizing the formula for differences in voting behaviour and other factors might help to avoid focusing on the problematic sites so much, and bring some smaller sites into the spotlight.