I have a playlist of over 9,000 songs. If I play the list on my PC (Windows 10, Spotify version 188.8.131.528.gde3fc4b2) the shuffle seems to work correctly. If I set playback to my Sonos speakers using Spotify Connect the queue changes such that it's only playing songs from a few artists in the shuffle. Please see attached screen shots, one from playing on the local PC and one from playing on Sonos.
We've passed this on to the right team and it's in their timeline for fixing. We'll close this for now as they don't need any other info from users.
There's no exact timeline available for a fix, but we'd recommend you keep an eye out for updates to the app. We'll always work to fix issues like this in app updates.