With a lot of hard work is the simple answer. I'm in a similar position, though most of mine are 96kb MP3pro's. I have many MP3's at different bitrates, no wavs, and no WMA's - if it's a WMA I don't want to know.
I dunno what you use to play your music, but I use Musicmatch
http://www.musicmatch.com/
which has various things you could do with, like tagging and renaming. It also converts some formats, but not WMA's. Failing that, I suggest you get seperate renaming progs and investigate other players - I'm not sure but maybe windows media player does tagging and genres and other stuff MM does - I don't use it so I wouldn't know.