It's not often I'd call myself "excited" about a program, but MusicBrainz Picard is a really great program. It lets you tag MP3s by looking the up in an online database.
That's very much like what a ton of other programs do, but the interface for this program is nice for doing a lot of MP3s all at once. The thing I really like about it is that it makes it easy to assign metadata to those MP3s that the program couldn't identify itself. It identifies what MP3s it can, and then displays a list of albums that it thinks the identified MP3s belong to. You can drag-and-drop unidentified MP3s onto the correct tracks in those albums manually to tell it what to do with the songs it missed.
The other nice thing is that it works well for tracks with non-English metadata. My many folders full of Japanese music were easily identified by this program and filled in with correct Japanese titles and artists and album names. Whatever tagger I'd used in the past (I can't even remember now) had used horribly mangled Engrish romaji for metadata, which was always disturbing.
The only thing that's annoying about right now is that this program is a QT4 app. This is the first QT4 app I've used, and I can't figure out how to set a QT4 theme, without installing KDE4 which I don't want to do. So the GUI looks horrible. I'm sure the GUI looks nice when it's using a proper theme, but even with screwed-up fonts and colors the program is very usable.
This program is in Portage of course. It apparently has some heavy Python dependencies on top of QT4, but such is life.