[MacNeo]

Partiamo dai dati tecnici.
L'iPod Shuffle legge: MP3, AAC, WAV e AIFF. Rispetto ai due modelli "maggiori" quindi gli manca soltanto il formato Apple Lossless.
WAV e AIFF li scartiamo perché occupano parecchio.
Restano MP3 e AAC.
Se vuoi la qualità migliore, usa AAC. Dal 160kbps al 256kbps direi, dipende quanto hai l'orecchio "allenato" (caso mai ti fai una paio di prove all'inizio così giudichi direttamente).

Le cuffie dicono siano un po' meglio delle vecchie, comunque se punti alla qualità sicuramente ne vorrai prenderai delle altre. Sono comunque auricolari che valgono neanche 10€, fascia medio-bassa quindi.

Sul software è sicuramente possibile usarne altri... però onestamente se fossi in te proverei prima iTunes. Visto che parli di una gran quantità di canzoni, un sistema che ti permetta di importare tutto e tenere ordinato l'archivio in modo molto preciso è a mio parere un gran vantaggio.