What you can do is adding all your music files to iTunes and let iTunes organize the folders. It puts it in this way: Artist->Album->01 name
You can also use ID3-TagIT or Tag&Rename for renaming using ID3 tags.
Btw:
For your PS3 you could use this:
http://code.google.com/p/ps3mediaserver/ it claims it can browse rar/zip as a folder and stream music/movies from it
Edit: Hmm it seams this is only a way to stream TO your ps3, not FROM... I guess you'll have to install Ubuntu on your PS3 first. You can use Mediatomb on your NAS for .rar/.zip file (search for mediatomb transcoding) but I don't know if it will be fast enough. Of course you can always extract the rar yourself using SSH or even using a script in a cron job which automatically unrars/unzips all rars/zips automatically and removes them afterwards.