I've been dissecting the shuffle algorithm and I have a basic idea of what is occurring. I have over 2305 songs starred and I always play a shuffle from my starred folder. Here is what I have noticed.
I have one song out of the 2300 that plays every day. It is the second song that I ever starred in Spotify. It is playing now, it played 22 songs before that, 62 before that, 5 before that, and 10 songs before that. That means that this song has played 5 times in the last 100 songs. It only has a 1 in 2,305 chance of playing at any time if you are completely random.
I often have songs by the same artist play within a few songs of each other. This is important because of the way I star music. I usually review all songs by an artist and star every song I like at one time.
I often have songs from the same genre and era queue near each other. This is again important because of the way I star music. When I look for music to star, I check out related artists so my starred list is usually segregated by genre and era of the music. I can tell when I get a lot of old country songs playing back to back or a lot of 90s rap songs playing back to back, that I starred those songs probably on the same day.
So here is what I think your shuffle algorithm does. It must put music into bins based on the date that I starred them. Then it will select a predetermined number of songs from within that bin. It is likely that the second song I starred is falling at the edge of a bin and therefore it is getting played in higher proportion to other songs since it only has to compete with the very first song that I starred.
I propose that you hire me on a temporary contract basis (I am a full time developer already) to fix your shuffling algorithm for all Spotify listeners to enjoy.