Después de meses de investigación resulta que el problema era una mala codificación del sonido por parte de las emisoras. Estaban comprimiendo demasiado el sonido y no sé por qué afectaba mucho más a unas canciones que a otras.
Al reproducirlo en el ordenador parecía que el problema se corregía debido a que tiene altavoces estéreo. Cuando hice grabaciones de canciones que se oían mal en el Galaxy M15 descubrí que en el ordenador se oían mejor y también en otros móviles que tenían altavoces estéreo se oían mejor.
Por suerte existen emisoras streaming que emiten en 320 kbps e incluso en FLAC sin pérdidas, así que me quedo con ellas.