No single program will do all that for you automatically, since all files are different in their own way there is no all-in-one utility that will set everything the way you want.
You should develop a habit of organizing files directly when you get/make them!
But that's not saying you have to do it all manually, which would indeed take quite a while.
Using a combination of programs will make it a lot easier for you.
Mp3tag as
mara- mentioned is a great program (probably the best one) to do most of the things you want, try it.
Other programs you may find helpful are programs to:
-Find and remove duplicates.
-Rename multiple files/folders easily, for example
Rename Master.-Play the files and be able to change tags and filenames directly inside the player, it can be done with for example
Quintessential Media Player.
Categorizing the files will be a bit more difficult if they aren't already tagged with genre, but there may be a program for that too.
Even if you use all of those programs you will still have to change the settings manually and make sure they do what you want. Otherwise you may end up with files organized/tagged/named even worse than before. It will take time, but doing a little once in a while will make it easier.
I've got 11000+ files of music and very few of them have incorrect/missing/awkward looking names/tags. I've used only
Quintessential Media Player and
Rename Master combined with Windows Explorer to do it,
Mp3tag would have made things even easier.