Ogg Vorbis is an audio codec developed to compete with mp3. It is completely patent and royalty free. It features variable bitrate encoding, stereo sound, psychoacoustics, and more. The code is currently being developed, but it looks good so far.
Info is at http://www.vorbis.com/.
In a non-scientific test, a 128 kbps Ogg sounded as good to me and my audiophile (and musician) cow-orker as a 256 kbit mp3. It seemed to be a bit heavy on the high-end, but after a bit of experimentation, we discovered that this was caused by the player. It upped the high-end to compensate for mp3s crushing it - but since Ogg Vorbis is more faithful, the player ended up overcompensating.