It's been under my skin for a long time now, but every single free music player app I've used in the past 8 years plays my locally stored mp3s in the exact same order each time the shuffle button is on. Many others complain about that too.
I don't know if it's happening on Android OS level, but even VLC, plays songs in the exact same predictable order. I've left support notes on VLC's forums, and submitted the issue to issue cues and there are no responses each time.
None of that encourages me to pay for a premium app, shuffle has been around since CD changers.
I would rather have the same "random" order than what Spotify does; random never plays some songs, and overplays other. I get true random has the possibility of that, but when I've heard the same song for the 4th time in an hour, on a 20-hour playlist, something is wrong.
I have this issue with youtube music only for some reason. For me "Shuffle" seems to be starting random, then after a handful of songs entering a loop of 6 or 7 songs. I never figured out why or looked it up, I just refresh the page. I know it must be only me somehow, but don't know what's happening.
Pretty much every USB music player has the same faults:
1. shuffle play does not work
2. crashes if there are more than N songs
3. does not find songs in subdirectories
All of these are trivial to fix. I do not understand the programmers who make the firmware.
My car's player (reading from a flash drive full of MP3s) doesn't have "shuffle", it has "random". The difference is subtle, but it means that each time it advances to a new track, it selects that at random. The result is that I never hear all the tracks in an album/playlist without hearing a bunch of repeats. Infuriating!
But when I play from my phone or PC, I use PlexAmp (backed by my Plex media server), which is the opposite extreme. Not only does it know what randomly shuffling is, but the server has analyzed the sonic profile of every track, and knows about similar artists and similar albums. So you can play an "artist radio" featuring that artist and other related stuff. And you can choose an auto DJ, which inserts between tracks the closest sonic match to the song it just played, or a brief detour of about 3 tracks that are spaced along the path from the track that just played to the one that's about to play. It's fantastic for discovering stuff you haven't heard in a long time within a very large library.
Is what you call the "shuffle button" a "shuffle playlist" button or a "shuffle mode" button? There is a subtle difference between those two and for what I understand you want the second
Amperfy for the Iphone randomizes the shuffle.
I just looked at the code and it's apparently using the Fisher-Yates shuffle with a call to arc4random each pass. It's literally eight lines of Swift!
I've never suggested this before, but if the Android app store has truly been as bad as you claim for as long as you claim, you should seriously consider buying an Iphone to solve your problem.
Auxio music player[1] for Android shuffles a new order each time the shuffle button is clicked (and ime is excellent for handling well-tagged libraries).
foobar2000 for Windows also changes the shuffle order but (at least in earlier versions) only after a relaunch.
[1] https://github.com/OxygenCobalt/Auxio