What about tacking a seriously "new boosted" and possibly randomized 10-30 submissions, clearly marked with different background to the end of frontpage, maybe after "next page" buttons? It would hardly make a dent to the load time, and people would in theory not feel as cheated since they know what to expect. It would still give "new" section a lot more eyeballs to find the golden nuggets.