I solved this problem by creating a smart playlist that only includes songs I haven't heard in X days. I actually went further and made it include 5-star songs I haven't played in X days, 4-star in X weeks, and 3-star in X months. I hear the songs I like the most, but the constantly updated list prevents the "random" shuffle algorithm from picking the same songs too often.
