Also einerseits gibt es Hardware mp3-Decoder, die einem viel Arbeit abnehmen können, aber mit einem ausreichend starken µC kann man darauf auch verzichten...

Es gibt zu diesem Thema - neben zahlreichen Hobby-Projekten - auch eine Application Note von Atmel: AT91SAM Internet Radio
Das ist von der Funktionalität natürlich erheblich umfangreicher als das was du machen willst, aber man kann ja problemlos auch Einiges weglassen.