When re-harmonizing a melody, one of the oldest tricks in the book is substituting the dominant (usually V7) with a major chord a diminished fifth above it. It is usually the last trick a jazz pianist is taught, for a very specific reason. It is so easy to do, and so effective, that many pianists out there don't learn anything else. The problem is that after hearing it so much, it just screams of cheese. I think it actually catches me more by surprise when a pianist uses a regular V7 instead of the tritone substitution.
When playing a melodic solo, one of the oldest tricks in the book is playing a whole tone scale on top of the dominant chord. It kind of turns the dominant into a V7 with an augmented fifth. It is also the only thing about harmony that many mediocre horn players bother to learn.
For the love of God, learn some new tricks. You can substitute every single chord in a progression with its "ii-V-I". That leads to the typical I-iii-VI-ii-V-I progression in which all you are really doing is branching the "ii" into it's "ii-V-I" (which in the original key would be "iii-VI-ii"). Once you do that, you can use tritone substitution on that "VI", since it is actually working as a dominant for the "ii". There are so many possibilities in jazz harmony, that it really sounds lazy and cheap hearing the same stupid substitution over and over again.
The circle of fifths is your friend when trying out new harmonic progressions. Just give it a spin through the whole circle. When you play something in more than one key, you are learning the idea behind the harmonic progression, not the actual chords. That is very useful for classical pianists too. Transposition is a huge aid to memorization, it helps you understand what is going on. You learn the actual functions of the chords, and not the notes in themselves. As a jazz musician, it is very easy to get bogged down repeating over and over the same cute tricks without realizing that you are doing it. Mastering new harmonic progressions or solo patterns seems like forced labor, but what it actually gives you is freedom. Freedom from the cage of cliches into which you force yourself because of ignorance.
[caption id="attachment_244" align="alignright" width="215" caption="The circle of fifths is your friend."][/caption]
Also beware of signature chords, usually dissonant, and usually way overused. They are sometimes cool, but lots of pianists tend to find a chord or a run they can play comfortably and shoe-horn it into everything they play. It's the same case with the trumpet player who just realized he can hit a high-E and even give it a nice shake. He will play anything, even a slow ballad, and force the damn thing in there so everyone can see his nice new trick. The music turns into a succession of cute tricks, instead of an actual artistic enterprise.
To open your harmonic horizons, analysis of jazz standards and Gershwin songs is a must. I also really recommend listening to and playing a lot of Bill Evans. He will either use quartal harmony, or he will use really normal triads, but in very intelligent and interesting ways that show you all the possibilities in simple three-part harmony. Something classic like Waltz for Debby uses harmony that is very simple on the surface, but treated in a way many jazz pianists avoid, almost as if it were something from Chopin or Schubert; and it will sound really awesome too.
And unlike many jazz pianists, the man had a beautiful round tone as well. I would kill to have that piano sound for Chopin, Grieg or Mozart. Miles Davis said it best. Bill played the piano the way it should be played.