Hacker news has a nice solution to this problem. New comments appear at the top of the thread, and then slowly fall unless they get votes. I think this works very well, although I think it's still a bit too far on the exploitation tradeoff.
I've thought about how to solve this problem, and I think the best solution is votes/time since the comment was posted. New comments will immediately appear at the top, since they have infinite vote/time ratio. But they will quickly fall to their correct ranking.
There are other solutions, like treating it like a multi-armed bandit problem. And you can use something like https://en.wikipedia.org/wiki/Thompson_sampling . Create a probability distribution for the upvote/downvote ratio for every comment. Sample from that distribution, and rank the comments accordingly. This should be close to optimal, but it requires people to use the downvote button lots (because it measures comment quality by upvote/downvote ratio, which is what reddit does currently.) Without downvotes, you could use time again, and create a probability distribution for votes/time.