MP3 é a aposta mais segura. Muitos dispositivos usam o AAC / M4A nos dias de hoje, mas isso realmente depende do dispositivo - quase todos os que você mencionou seriam capazes de reproduzir o AAC para determinados além do Xbox :
You can play MP3 files from your iPod on any Xbox 360 console. To listen to music stored in the Advanced Audio Coding (AAC) format, you need to download the free Optional Media Update from Xbox LIVE (see the steps below).
No entanto, gostaria de salientar que a transcodificação de seus arquivos de áudio causa alguma perda de qualidade, então, idealmente, você desejaria re-extrair os arquivos de sua origem (por exemplo, um CD), se possível.