If the loss of a reputation point really is one of the main motivators behind the lack of downvoting, then I guess making it free or cheaper is indeed the way to go.
How about not making it entirely free though, to keep a tiny safeguard in place? Like, making every 5 or 10 downvotes cost one point?
The normal rep count would continue to be displayed as an integer; for those who really need to know, the exact number could be displayed privately on the profile page, much like flag weight.
Just to offer another option. I'm not sure - completely free downvoting may indeed be the answer. It would see more abuse as a tool in personal conflicts, but that happens already and the net benefit is likely to vastly overshadow that.