It seems that the main reason we like music so much could simply be that we love recognising patterns, and predicting what will happen next. If this is the case, then all music has to fall somewhere between two extremes: on the one hand, it cannot be too repetitive (such as a drum machine stuck repeating a single bar's worth of a rhythm) because it would be too easy to predict; on the other hand, it can't be completely devoid of repetition (such as playing completely random notes at random intervals). This means that some variation is necessary, but the real craft is in getting the balance just right.
Getting the balance right also appears to apply to other forms of entertainment: an unusual story shouldn't also be written in an unexpected way, such as the second person point of view, as the combination would overwhelm the reader.
Getting back to music, it seems like the key to composing an accessible song with artistic merit is to experiment with one element of the song, while keeping the others within the confines of what the listener is likely to expect. For example, David Bowie's song Sound and Vision, produced by Brian Eno, has an interesting and unexpected arrangement which doesn't let the vocals appear until the end of the song. They get away with this because except for this quirk, Sound and Vision is a pretty normal pop song.
On another level, the very essence of a song is varying some parts while leaving others alone. With most genres, especially rock, this involves keeping the instruments the same (an acoustic drum kit and several electric guitars, for example) while varying the melody and changing the chords, flitting back and forth between the verse and chorus, occasionally throwing a bridge into the odd song.
One genre which probably gets most criticised as being repetitive is techno, where whole pieces of music can be built around just a single chord and a single bar's worth of rhythm, albeit with breaks in predictable places (bars which are a power of two, to be exact) for variation. The rhythm and melody certainly don't change much, but they don't need to, because other parts of the music are changing instead.
Many pieces of music in various subgenres of techno and house (particularly ambient techno and acid house) don't have verses or a chorus. Instead, various instruments are faded in and out (for a good example of this, see Aphex Twin's album Selected Ambient Works 85-92), or layered on top of each other (as is the case with many of Underworld's crescendo based songs, particularly Cowgirl). Instead of a sudden change from one pattern to another, the fade or buildup is subtle and evolving. This isn't better or worse than the verse and chorus based structure of almost all pop music; it's just different.
The acid line provides another important type of variation in music: a sound passed through a filter with a constantly changing cutoff point. This technique uses a single instrument, yet the instrument's timbre drastically changes over time (the only acoustic instrument I can think of that has such a diverse range of timbres is the Jew's harp). This slowly evolving sound can appear so interesting that even a single note played constantly on the instrument can provide enough of a context for it to sound good (such as the acid line in the background of Madonna's song Ray of Light, produced by William Orbit).
There are many other ways of changing the timbre of a synthesiser's patch subtly over time, but the result is always similar: the slow evolution of a sound. By changing the timbre of an instrument while playing it, and by fading various instruments in and out, a suitable amount of variation can be achieved even while playing repetitive patterns.
If you think that techno is repetitive, then bear in mind that fans of the genre might find rock to be just as monotonous: it uses the same handful of sounds in album after album. But either of these ways of thinking would be a shame, as one of the inspiring things about music is how it encompasses such diverse forms of expression. Every new genre that exists only serves to make music more awesome, by making it even more expansive. This should further inspire musicians to live up to the challenge to push it further in new directions.