> no tune was played twice until all of the tunes were played... That doesn't sound random. I use Google Play Music and it "randomizes" things in the way you desire. It takes your playlist and shuffles the entries; you can even press a button to see how it's sorted it. That ordering sticks around forever if you take no further action, though, so it will repeat that random ordering indefinitely unless you press the sh…
If its programmed like youtube, it only shuffles the last 100 you have visited in your list, not the whole list.
Not sure exactly what you're referring to here, but on Google Play Music, there's a concept of a "queue" of music that's currently playing/has been played. Generally it's just the songs in order of the album/playlist/etc. where you selected the song to play, but you can also manually add/delete/reorder the songs on the list. Since it keeps track of the songs that were played previously in the queue (to enable the "previous track" button, among other things), enabling shuffle just reorders the queue in a random way (with the currently playing song first). From the few times when I've used it with extremely large lists of songs (e.g. my entire music library), it doesn't just shuffle a subset of the queue that you have currently active, but the entire thing. You can also choose to start playing an album/playlist/etc. shuffled, which just puts the entire thing in the queue in a random order and starts playing through it.