I like Tag&Rename (T&R) but it will not automatically select an appropriate genre given a particular song. Therefore, the following will require some input on your part. If your genre requirements are somewhat broad it shouldn't be too bad. I only use about a dozen broad genres: Rock, Blues, R&B, Folk, Country, Bluegrass, Jazz, Classical, Vocal, Easy Listening, Gospel, Soundtrack. Allmusic.com uses only about 20 (which are further divided into styles):
http://www.allmusic.com/cg/amg.dll?p=amg&sql=73:pFirst, organize all of your mp3s into an appropriate genre folder.
Then, using T&R, select all the files in one of the genre folders;
set T&R for that genre;
make sure only the T&R genre field is activated;
click T&R's "Save tags" button;
repeat for the next genre folder.
Other tag editors are also available that can probably do the same thing.