Here's an idea that I got when playing with the 'weighted random' feature: Would it be possible to shuffle a playlist in a distributed way? Meaning, it would try to play every artist once before it played any artist again. So let's say you had a bunch of artists with one song each, and one artist with 8 songs. The playlist would try to play 8 different artists before it played the one with 8 songs, so the recurrence would be distributed across the playlist.
The idea is that you're always getting variety, like on the radio where they (hopefully) wouldn't play the same artist twice in a row, or twice within a 20 minute period, et cetera.