In reply to:
Is there actually a difference between the many different ones?
Short answer: Yes.
Long answer: The quality of any given MP3 stream is entirely dependent upon the encoder used to produce it. The reason for this is that the encoding process involves analyzing the original audio data with a human psychoacoustic model and using the data from this to decide what parts of the frequency spectrum are most critical to encode most accurately. The psychoacoustic model and related algorithms are not part of the MPEG audio standard, so encoders have a lot of flexibility and vary in their ability to deliver good quality at any given bitrate. Keep in mind that "quality" is also highly subjective.
I don't have any specific advice for encoders, but I can tell you there are really only a few different varieties, most based either on the ISO reference encoder or the Fraunhofer encoder. The Fraunhofer encoders are generally considered to be superior at encoding with lower bitrates. I'm sure others can offer much more specific advice.
For some related information, see this post.
A big stumbling block for authors of encoders is the fact that many of the algorithms used in the psychoacoustic model are patented. This is one reason there aren't very many different encoders (based on independent code, not, for example, licensed from Fraunhofer.)
-v