toda compactação de arquivo, resulta em perda de qualidade, por isso deve ser bem avaliado
http://en.wikipedia.org/wiki/Comparison_of_file_archivers
Na verdade existem algoritmos de compressão com perdas e sem perdas. Quando você usa compactadores como os conhecidos zip e rar, por exemplo, você não tem nenhuma perda de qualidade porque eles fazem compressão sem perdas. Já quando você ripa seu CD de áudio para mp3 você estará perdendo alguma qualidade porque mp3 usa compressão com perdas.
Quanto a redução no tamanho do arquivo, obviamente que depende do algoritmo utilizado, mas também depende muito do arquivo que está sendo compactado.
Os algoritmos de compressão sem perdas conseguem reduzir o tamanho de um arquivo porque eles "jogam redundância fora" que pode ser completamente recuperada mais tarde a partir do que restou quando você descompactar o arquivo. Tipos diferentes de arquivo possuem diferentes quantidades de redundância e consequentemente vão resultar em diferentes taxas de compressão. É por isso que compactar o mesmo arquivo duas vezes não resulta em praticamente nenhum ganho (quase toda a redundância que podia ser jogada fora sem prejuízo já foi jogada fora na primeira vez, a menos que o algoritmo usado não fosse muito bom em "detectar a redundância" e deixou passar muita coisa).
Já no caso de compressão com perdas além da redundância você está jogando fora alguma informação útil também. Dessa forma não será possível recuperar o arquivo original de maneira fiel mais tarde. Mas muitas vezes isso vale a pena para reduzir ainda mais o tamanho do arquivo. Esse é o caso de quando você converte seu CD para mp3, por exemplo. A conversão pode jogar fora tranquilamente frequências que não contribuem muito para o som que você está escutando (fora da faixa de frequências que o ser humano escuta, por exemplo). A "qualidade" que você pode escolher quando você ripa seu CD está diretamente relacionada a quantidade de "informação útil" que você permite que o conversor jogue fora e, claro, ao tamanho final que o arquivo vai ter.