At first I thought your question was exactly what I wanted. ... Nobody actually adressed the "random" in the first line. I know it wasn't exactly part of the actual question, but... I wrote this:

bash$ echo install File::KGlob | sudo perl -MCPAN -e shell
bash$ perl -e 'use File::KGlob qw /kglob/; \
>        @files = kglob("/mp3/*/*"); \
>        while(@files) { $i = int(rand @files); \
>        `mpg123 $files[$i]`; \
>        @files = (@files[0..$i-1], @files[$i+1..$#files]); }';
[download]

'course, your directory structure has artist too... mine doesn't. So you'd need that kglob to have another '*' in it.