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.
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.