My music teacher told me that one property of great music is that it is both surprising and inevitable - you don't expect something, but looking back you see that it has been carefully prepared for. Is there a more formal understanding of this principle or a source of examples with explanations? And how do I deliberately use it in composition?
One approach may be found in the Implication-Realization Model by Leonard Meyer and Eugene Narmour.
In short, there are five proposed governing principles that suggest what listeners expect from a given musical excerpt. How we perceive the music is then based on either the attainment or the denial of the expected events.
In other words, a musical excerpt implies some continuation, and our cognitive response depends upon whether the subsequent music ever realized those implications.
You may be interested in Leonard B. Meyer's book Emotion and Meaning in Music. See also What causes notes to appear to follow a progression of melodic expectations? How does this work?
For me personally, the music of Samuel Barber is my favorite example of what you describe. So often I expect his melodic lines to do one thing, but when he does something different, I realize his choice was better than mine. If this is the type of music you're interested in, check out his Violin Concerto and his Essays for Orchestra.
I'm a big fan of Beethoven's symphonies, and I think he was a master of this.
I listened to his 9th symphony (through the free service by the St. Paul Chamber Orchestra's website) like a dozen times in the last few years and this symphony really digs deep into this principle. After the first three movements, there's a time when the low strings seem to be having a conversation, and they "bring up" (as in conversation) little distinctive snippets of the first three movements. Then they seem to propose an alternative: the primitive melody of the final movement, the "ode to joy" melody.
Other stuff happens, then finally the big chorus arrives. Beethoven intentionally makes the entrance messy, in the middle of another measure. I would say this was to show how his big chorus is not just different from the other themes, but has defeated or dominated over and above the other themes like a ship moving through ocean waves.
The "ode to joy" melody of the big chorus had been signaled in advance by the low strings, but there was no way for the audience to know in how many ways the composer would be working, turning, ornamenting, re-engineering, beautifying, amplifying (etc) that theme... unless they remembered what Beethoven was capable of and said to themselves, "I bet that little melody is gonna turn into something great."