I use Tag & Rename. I absolutely love it. I know one of your requirements said "free" but I had to throw this out there anyway. $29.95 is a little steep but there's a 30 day trial with the only limitation being a nag screen on startup if you want to give it a shot.

http://www.softpointer.com/index.htm

i have a huge mp3 collection as well and didn't start organizing them until i had about 8000 or so files with missing or inaccurate tags. just take it slow at first...it's a LOT of work.

cover art is a tricky issue...you REALLY need to do some research on how the program you're using approaches it. itunes stores covers in its own database and adds a code into the "comment" field of the mp3 that calls the cover when you use itunes. Obviously, not many other programs understand this garbled comment and covers don't show up. you need the image actually inserted into the "album art" field of the ID3tag.

I'm not totally positive how Tag & Rename's cover feature stacks up. I know it can access amazon and other sites (like most programs that say they retrieve covers do).

I've been adding covers manually mostly because a lot of my albums are rare and I have to scan them in from my personal collection anyway