"Negative votes" as stated would not prevent the Spoiler Effect. e.g. if a centre-right voter negative-voted a far-right candidate, that's one more vote, effectively, for the left side of things, and vice versa. Additionally, if you positive-vote your side, your side is up one vote, but if you negative-vote your side, you're down one vote. Which is a net difference of two votes, not one. So you're actually harming your side by even turning up. This really does nothing to help third parties grow.
IRV (instant run-off voting) is a good simple system that eliminates the spoiler effect completely. This helps small parties to run candidates without being attacked by their own "side".
MMP (Mixed member proportional) voting takes all the "loser" votes, and gives them additional members in the legislature to make things proportional. e.g. if the greens got 10% of the vote in every single seat, then they get extra members such that they get 10% of the representatives in the legislature. As such, it gives a proportional voice to all the "losers". It therefore makes gerrymandering completely pointless.
Anyway, even without MMP, you can get rid of gerrymandering by basically "automating" the process. Have some arbitrary set of criteria for what counts as a better set of borders. e.g. add together variance of population sizes and length of borders (shortest is best), and the lower that number the "better" the plan is. A number of states already use rules like this to determine which electoral map is the best.