Blues has a fairly strict formula in which most songs follow. Most songs are in 4/4, and most modern music sounds fairly similar yet people are really into it.
(BTW, I believe we're overly simplifying by speaking of music as a single entity. All of the elements you mentioned are a foundation in more popular music, but good luck finding them in more modern or experimental genres.)
The cognitive effort to digest Schoenberg is different from that for a pop song. Still, you can progressively familiarize yourself with a genre, and relax on pieces that seemed hard and inaccessible earlier.
Yes, as a passionate music collector and someone that can get lost in weird, obscure and very leftfield music, this is something I notice all the time. You start with something accessible only to find yourself enjoying obscure 70s synth funk recorded on tape in someone's bedroom months/years later. Or similar.
It's why we recommend "Kind of blue" whenever someone wants to get into Jazz, which is difficult if you just randomly start...anywhere.
The mere score of a blue piece is just as good as useless for conveying the power of a particular blues performance for example.
Most 12-bar blues use a similar chord progression but have different melodies. Even the same song performed by two different musicians will sound different enough to be perceived as "novel".