I agree that introducing randomness would probably make it more fair to new posts. One idea I had, rather than an algorithm based on Bayesian prior probability estimates, would be one based on a Kalman filter (or similar) confidence interval from the up/down vote history.

The filter would give a range of possible scores for the post -- ones with few votes would have a very broad range, ones with lots of votes would have a tight range. Then you order based on a random number in that range (discounted based on its age).