A truly random shuffle can play the same song twice.

Not true with a “deck shuffle”, which is how playlist shuffle should work. Google Play Music worked that way and it was fantastic. Each song only exists once in the playlist, a deck shuffle just moves them around.

A truly random shuffle can play multiple songs from the same artist in a row.

True, but I find that to not be any different from the current “not true random” shuffles. Spotify still does that to me all the time.