Появилось достаточно много форматов хранения аудиофайлов, запутаться можно.
Куча статей по преимуществам того или иного формата, в которых новичкам трудно разобраться.

Так что же лучше для хранения музыки на компе или на плеере?

И чем отличается MP3 от MP4 например?

Небольшая каша в голове...

Итак, начну с азов.

Есть два больших класса аудиокодеков - без потери (lossless) и с потерями (lossy).

1) Безпотерьные - позволяют после сжатия-распаковки оригинального wav (не сжатый аудиофайл) получить на выходе его же неискаженным.
Такие RAR или ZIP для музыки - упаковали-распаковали - получаем тоже самое.

2) Кодеки с потерями - позволяют уменьшать размер файла посредством удаления некой информации. Типа - тихий звук маскируется громким - его не слышно. Поэтому из огибающей можно вычесть (т.е. убрать т.к. Вы всё равно его не прослушаете). После этого получаем на выходе упрощенный аудиофайл, поддающийся упаковке. Естественно, после распаковки сжатого файла получим отличающийся от оригинала.

1) кодеки без потери качества оригинального трека (CD)

- FLAC
- APE
- WavPack
- есть APPLE LOSSLESS и WMA LOSSLESS - фигня, т.к. требует специального плеера (не универсален)

2) кодеки с потерей качества оригинального трека (CD)

- MP3
- OGG
- MP4 (он же ACC)
- и прочая хрень

3) кодеки комбинированые: например TTA - при кодировании им получаем два файла - часть с потерями и довесок - часть для точного восстановления.

пока каша или как? 

Итак, в чем слушать?

Имхо, на компе с наушниками типа ГЕНИУС и встроенной звуковой карточкой, колонками за 2000р вполне достаточно МР3 с высоким битрейтом - как минимум 192кбс.
Портатив... Да, плееры сейчас поддерживают FLAC, но скажите честно - услышит ли кто разницу в гремящем-скрипящем транспорте или на зашумленной улице.
Поэтому в большинстве случает не надо ипать себе мозг и спокойно слушать MP3 256 кбс (IMG:style_emoticons/default/smile.gif)

В чем хранить?

Лично я архивы храню в формате MP3 320kb/s по крайней мере, самый распространенный сейчас формат и проигрывается везде. А интересные и реаритетные записи пишу на CD и убираю в специальный альбом. Выкладываю в 192kb/s - для интернета ОПТИМАЛЬНО.
Моя аудио-библиотека насчитывает уже около 100gb джаза и тубной музыки, есть любимые, которые могу слушать постоянно и просто "до кучи". Но всё прослушал.

Всяких альтернатив по кодированию лучше избегать.

если я не прав - переубедите меня.