>I have this issue with youtube music only for some reason…

Try navigating to the playlist and look below the currently playing track. There should be a "shuffle type" button bar showing 'Familiar', 'Discover', 'Chill', etc. It seems to produce better results for me if I explicitly choose familiar tracks or discover mode (or the other options, but i use the first two 99% of the time).