It's worth considering how the brain rewards problem-solving with a little burst of endorphins.
So you get a little boost from things like:
Recognising a song.
Recognising an artist performing something you haven't heard before.
Guessing what a song will do next.
Spotting an unexpected pattern (e.g. anticipating a repeated change).
Recognising a familiar element in a new piece.
And so on. It's why these endless 'Taco Belle' sorry, pachabele medleys are so popular...
Quite a lot of such things (but not all) involve recognition, so we tend to prefer new things that have an element of familiarity.