iTunes inizia a riprodurre ciò che è attualmente selezionato. Per me, ad esempio, la playlist selezionata era "Più recentemente aggiunta", quindi quando premo il tasto play sulla tastiera, inizia a suonare la prima canzone da questa lista.
L'unico modo che conosco per risolvere il tuo problema è abilitare la riproduzione casuale in iTunes.
È possibile farlo facilmente facendo clic sul pulsante freccia a forma di serpentina accanto all'immagine di copertina nella vista superiore. Se è evidenziato in blu, la riproduzione casuale è attiva.
Se esci da iTunes e premi nuovamente il pulsante di riproduzione, verrà riprodotta una canzone casuale dalla libreria.
Svantaggio: ogni volta che lo hai cambiato (perché non vuoi avere una riproduzione casuale ma vuoi ascoltare un album) devi ricordarti di abilitarlo di nuovo prima di chiuderlo.
AFAIK non esiste alcuna impostazione di preferenza per questo.