This would first require fixing your randomisation to perhaps (if mathematically possible) not repeat artists for a while, as the current randomisation in Spotify does not work *at all*.
A video I made to show this: https://www.youtube.com/watch?v=Qmay2gXJMSQ&feature=youtu.be
But further, while fixing this, a feature I think that would really set Spotify apart would be the ability to do weighted randomisation. This would require the ability to rate songs (perhaps on a 5 star scale), and then Spotify could have a smart randomisation feature that not only makes sure it doesn't duplicate songs/artists in a specified period, but also plays higher rated songs more often than lower rated ones.
Alternatively, (and perhaps this is for another post), a public API for writing our own apps in the Spotify ecosystem so I can implement this stuff myself.
Updated on 2019-08-24
The shuffle function discussion is located here, and only one thread can exist per idea:
Regardless of status, please vote for it, and add a comment there, so it may be improved. Any update on the matter should be posted there.
You might find this article interesting too.
Please check this related Ideas too:
For more info on how the Ideas Board works, click here. :)