For Windows, WinAmp will do at least part of what you want -- you can select a swath of files after you've added them to the Library, and right click them to "Send To " that will cause WinAmp to take each MP3 file, run it against the GraceNote database, and bring back the appropriate ID3 tag data to write to the MP3 file. And WinAmp looks like it should make custom playlists without too much work. For Linux, the combination of Amarok with MusicBrainz/Picard will do about the same thing.
One caveat: the ID3-tagging apps apparently look for some sort of "watermarking" data embedded in the audio that doesn't get lost when the CD is ripped to MP3 -- that's how the GraceNote entries are located. But some older or indie music simply won't have the watermarking, so you could get some Very Wrong tags coming back. Still, overall I found the success rate to be pretty high.
One caveat: the ID3-tagging apps apparently look for some sort of "watermarking" data embedded in the audio that doesn't get lost when the CD is ripped to MP3 -- that's how the GraceNote entries are located. But some older or indie music simply won't have the watermarking, so you could get some Very Wrong tags coming back. Still, overall I found the success rate to be pretty high.