The first thing we added was the "rising" page, which used to be reddit's default "new" page. The rising page was a weighted new page. It was a little hacky, but worked for a while. I see they've changed this, which I think may have been a mistake, but I haven't thought about it in forever.
The second thing we did, which worked really well, was to have an up-and-coming link placed at the top of the list on the frontpage. This helped those borderline posts get more visibility. I had a reddit simulator I used to use to test things like this. That space appears to be a subreddit search box for me, so it seems they've moved onto another solution.
Randomness is an interesting idea, though it might be a bit difficult to fit into the way we cached things.