Depende de algumas coisas. Há vários tipos de formato, e citarei alguns deles:
Não comprimidos: Desconsiderando

toda a parte técnica da coisa, eles representam o áudio original e têm o maior tamanho. Exemplos: .wavs e .raws.
Comprimidos: Alguns têm maior grau de compressão, outros menor: seria o "quanto eles diminuem de tamanho" a grosso modo. Dito isso, podemos separar em "comprimidos sem perdas de dados" (lossless) e "comprimidos com perdas de dados" (lossy).

Os lossless representam compressão não destrutiva, ou seja, todos os dados podem ser recuperados. Seu tamanho é menor do que os não comprimidos e apresentam a mesma qualidade. Os formatos mais famosos são o FLAC e o MP4.
Os lossy são destrutivos, ou seja, são uma aproximação do arquivo original. A qualidade é "pior" mas o tamanho é ainda mais reduzido. Exemplos famosos são os formatos AAC e MP3.

O Bitrate, diferente do que o @Sensato_b falou, não é um fator tão determinante assim. Na verdade, a parte mais importante é o equipamento que se utiliza para escutar além de, claro, a sensibilidade do ouvido da pessoa. Se for um fone de ouvido qualquer ou caixas de som, é extremamente difícil ou mesmo impossível notar alguma diferença entre 128 kbps e 1411 kbps.

Portanto, 128/256/320 kbps tá de ótimo tamanho pro usuário comum, que não notará diferenças. Se ainda assim quiser testar teu ouvido, é só baixar um FLAC e um MP3/AAC da música e tentar achar diferenças (Aqui um exemplo: https://mega.nz/#!Dkhh0ASS!m5BCKMpx2SsrINFzjITI1lZKPD0m0NFqXzEORtKovyA )
Mas já adianto que a probabilidade de você notar as diferenças e acertá-las num teste duplo-cego é de 1 em 10.000.000 usando uma distribuição binomial.