Adam,
1.) this is possible via Mp3tag's Export feature. There is currently no configuration for M3U files in the archive, but I think you'll get the idea after looking at the other configurations. There is also a help topic on export configurations.
2.) Just click on the first column of Mp3tag's file view (the column with the icons) to randomize the order of the files. After that, simply export the list without specifying a field in the $loop-command.
Here is a (non-tested) example, but I think this will work: $filename(random_playlist.m3u)#EXTM3U
$loop()#EXTINF:%_length_seconds%,%artist% - %album%
http://url.com/$replace(%_filename_ext%, ,'%'20)
$loopend()
Please don't send me emails with the same questions you're asking on the forums!
Regards,
~ Florian