Nenhuma mágica, mas você pode fazer isso para evitar a cópia dos arquivos que já estão lá:
Crie sua playlist no disco rígido primeiro (deve ser bastante rápido, especialmente se você tiver ssd):
$ rm -rf /tmp/playlist; mkdir /tmp/playlist
$ find . -type f | shuf | head -1000 | tar -T - -cf - | (cd /tmp/playlist; tar -xvf -)
Em seguida, use o rsync para sincronizar o stick USB:
$ rsync -av --delete /tmp/playlist /media/foo/
Com um pouco de udev hacking, você pode fazer isso automaticamente quando o usb stick é inserido, pré-gerar playlists toda semana para agilizar as coisas (crontab), exibir uma boa barra de progresso enquanto está acontecendo e pode até ser fácil de usar =)