I recommend Ice Man as the first tune you master. It's only eight bars long and uses just two chords - the tonic and dominant 7th. You can pick it up from the YouTube performance by Tuba Skinny.
Very similar is Old-Time Religion. It's essentially just eight bars - six of them on the tonic and the other two on the dominant 7th.
For your first experience of a tune in a minor key, may I recommend Crumpled Papers? It's a very simple 12-bar (though not a blues). It is best played in D minor and you will probably get away with just two chords - D minor and A7th. You could pick it up by clicking on THIS VIDEO.
I recommend Eh La Bas and Mama Inez for playing even by a novice jazz band. Eh La Bas has a simple melody and is also entirely based on the two most familiar chords (tonic and dominant 7th). Mama Inez has a very simple chord pattern (using only three chords) and is fun to play. Let me also offer you Creole Song, Gatemouth, Jambalaya (On the Bayou) and Rum and Coca-Cola. That gives you quite a few easy tunes to learn and try out.
Creole Song consists of just 16 bars, divided into two 8s. The two little melodies are simple, catchy and repetitive. Play it in the key F and all you will need are two chords: F and C7th. Don't confuse this with Creole Love Call or Creole Love Song. I am talking about the tune you can find on YouTube played by Kid Ory and his Creole Jazz Band. The song Salee Dame is almost identical: perhaps they were originally the same tune.
Basically, the chord pattern is simply:-
F | C7 | C7 | F, repeated over and over.
F | C7 | C7 | F, repeated over and over.
Gatemouth was I think written by Louis Armstrong’s wife, Lil Hardin, and made famous by the clarinetist Johnny Dodds. It also has just two simple, repetitive sections, in this case 16 bars each. You can pick it up by watching the performance on YouTube of Gatemouth by the Peruna Jazzmen of 1988. The main theme (used for the improvisations) requires little more than the chords of Bb7 and Eb, though with the final four-bar sequence:
Ab :Abm / Bb : C7 / F7: Bb7 / Eb. This is a sequence you must learn, as it comes at the end of dozens of tunes, so it is worth the trouble.
Ab :Abm / Bb : C7 / F7: Bb7 / Eb. This is a sequence you must learn, as it comes at the end of dozens of tunes, so it is worth the trouble.
Jambalaya is great fun to play and SO simple. Play it in Bb and all you need is to keep repeating the sequence: Bb / Bb / F7 / F7 / F7 / F7 / Bb / Bb.
If you need reminding of the tune, try the YouTube performances by the Carpenters and by the Tierra Buena Jazz Band.
Rum and Coca-Cola is just as simple. Play it in the key of C and all you need is to keep repeating:
C / C / C / G7 / G7 / G7 / G7 / C .
This calypso-style tune was composed about 70 years ago by the Trinidadian Lionel Belasco. In the last few decades, trad jazz bands have adopted it with much success.
