The problem is then the signal-to-noise ratio decreases and therefore making the front page less attractive to new (maybe even to more experienced) users.
Its a tradeoff, but you can decide how far along the scale to go. Maybe 1 random story isn't really going to ruin everything, and maybe the value of a good algorithm that tested new submissions this way would be worth it overall. Maybe we are letting alot of good stories slip through the cracks because new doesn't get enough visits- so you might want to add more than 1 on the front page. You can hide point counts too- why do we even need to see the number?
Even allowing between 1, 2 and 3 new links seems like it could work. There are enough people that links would get a nice boost in being upvoted or downvoted.