"Random" doesn't necessarily mean "uniformly distributed random." Shuffling a deck of cards randomly is random, but you're not going to get the same card twice in a row, or even the same card twice until you go through the whole deck.
Do you re-shuffle after the deck is exhausted, or after every hand? It's not excessively unusual to be dealt the same card twice in two consecutive hands.
Who said anything about hands? I'm trying to make an analogy between shuffling a deck and shuffling xkcd comics. I thought having a visual, physical analogue would perhaps help in seeing that randomness still exists in a shuffle.
Sorry, the point I was trying to make was "shuffle" could possibly mean "re-shuffle after every track" - so you could still get the same track twice in a row.
Shuffling the whole playlist to choose a new song every time is no different than choosing uniformly from all songs every time. What would be the point? I can't tell what you are getting at.
And a uniform random shuffle chooses any of the N! orderings with equal probability. One is looking at a single element as the output of the process, and another is looking at the entire list as the output of the process.
Also, there are plenty of non-uniform random distributions.