The initial idea was to see which tunes improved from their first performance to the album versions; but there's no general answer - each song has its own history.
Some were excellent the first time out; others took a long time to settle into place; some were played for months before being recorded; others popped onto the stage fresh from studio rehearsals. Since Dead songs often took years to reach their full potential, it's rare to find a studio version that's the "standard" for a song. Early versions are usually rather bare and rough-edged, which makes them interesting to hear since our ears tend to fill in what's missing.
I may have skipped some songs inadvertently, so add a comment if any are missing. This list goes up to 1977, and is mostly limited to the Dead's original songs that appeared on albums (so a lot of their unreleased '66 songs are not included), and a few of the more notable covers up to 1967 that were released on albums.
A more complete listing of the Dead's early covers is here: http://deadessays.blogspot.com/2009/09/early-dead-covers.html
1/8/66 - Caution
http://www.archive.org/details/gd1966-01-08.sbd.bershaw.5410.shnf - our first live Caution, though there's a short studio cut from November '65. (This show also has our first Death Don't Have, which never changed much.)
January 1966 - Viola Lee Blues studio rehearsal
For most of the songs on the Dead's first two albums, we don't have "first" performances since so many shows are missing. 1967 was a year of nonstop rehearsals, so early versions of Anthem tunes like the Other One & New Potato are very similar to the album recordings. Viola Lee's unique in that we have the rehearsal BEFORE the first live version, which is here (track 16, along with a couple slightly later versions) -
January 1966 - I Know You Rider
http://archive.org/details/gd1966-XX-XX.sbd.GEMS.81254.flac16 (track 17)
A cover never released in a studio version, but this list wouldn't be complete without mentioning our earliest live I Know You Rider (which is similar to the Nov '65 studio demo).
5/19/66 - Cream Puff War
Cream Puff War was played throughout '66, and this one's the earliest (there's another early one on the Rare Cuts CD). This show also has our first Hurts Me Too, Sittin' on Top of the World, New Minglewood Blues, and Good Lovin'.
3/18/67 - Golden Road
Unfortunately, we only have a couple performances of Golden Road, from after the album release.
As for the other cover songs on the first album -
Early 1966 - Good Morning Little Schoolgirl, Beat It On Down The Line
http://www.archive.org/details/gd1966-XX-XX.sbd.GEMS.81254.flac16 (track 5)
Schoolgirl was one of Pigpen's earliest numbers, and in fact our first Schoolgirl from early '66 is also the first Dead medley, sandwiched with You Don't Love Me. (This set also features perhaps our earliest BIODTL, track 13.)
3/12/66 - Cold Rain & Snow
1/14/67 - Morning Dew
(However, the version on this tape actually dates from late '68, so the first live Dew we have is actually the one from 3/18/67 - http://www.archive.org/details/gd67-03-18.sbd.fink.10282.sbeok.shnf )
6/18/67 - Alligator
http://www.archive.org/details/gd67-06-18.sbd.mandrake.19586.sbeok.shnf - a primordial version. (A couple earlier dated tapes are misdates.)
7/23/67 - Turn On Your Lovelight
http://archive.org/details/gd1967-00-00.125314.sbd.studio.sorochty.flac16 (studio rehearsal)
http://archive.org/details/gd1967-07-23.aud.sorochty.125462.flac16 (at the end, cut off)
A later performance was released on Live/Dead, but these early versions are quite different.
8/4/67 - New Potato Caboose
http://www.archive.org/details/gd67-08-04.sbd.hanno.16752.sbeok.shnf - I think this is the earliest New Potato we have (though some are misdated earlier).
This show (and 9/15/67) also has the earliest show-ending Feedback.
10/22/67 - The Other One
http://www.archive.org/details/gd67-10-22.sbd.miller.18101.sbeok.shnf - different lyrics.
1/17/68 - Dark Star, China Cat, The Eleven, Born Cross-Eyed
Dark Star had already been recorded for the single, so this is an example of a live debut that's close to the studio version, but sounds very undeveloped since they kept expanding it for years.
China Cat, on the other hand, wouldn't be recorded for another year, and these early '68 versions are not only in a different key (so Garcia sings strangely) but are paired with the Eleven.
1/20/68 - Clementine
A short-lived song that didn't make it onto an album, though they played it now and then for another year.
May/June 1968 - St Stephen
We're fortunate to have a few Stephens from spring '68, shortly after its debut. 6/14 is the best, but these are in SBD quality. Many differences from later Stephens!
Most of the other Aoxomoxoa debuts don't sound too different from the album versions, since they were played at the same time they were recorded.
But for the record:
10/8/68 - Cosmic Charlie
http://www.archive.org/details/gd68-10-08.sbd.belaff.17691.sbeok.shnf (Hartbeats, great!) +
http://www.archive.org/details/gd69-01-17.sbd.miller.89798.sbeok.flac16 (Dead debut)
12/7/68 - Rosemary
http://www.archive.org/details/gd1968-12-07.sbd.miller.88674.sbeok.flac16 (only one)
12/20/68 - Mountains of the Moon
1/24/69 - Dupree's Diamond Blues (with harmonica), Doin' That Rag
(The 4/26/69 encore of What's Become of the Baby could count as a live version - Bear was playing back a studio tape on the PA while the band played feedback.)
June 1969 - Casey Jones, Dire Wolf, High Time (Garcia solo versions)
http://www.archive.org/details/gd1970-01-01.studio.smith.91324.sbeok.flac16 - studio demo
6/7/69 - Dire Wolf
But a more interesting alternate early version (Jerry on Pedal steel, Weir on vocals) is here, from 6/27/69 - http://www.archive.org/details/gd69-06-27.sbd.samaritano.20547.sbeok.shnf
6/21/69 - High Time
These early versions are quite wispy.
6/22/69 - Casey Jones
The early versions have a neat jam into the song, and this one's the best.
8/21/69 - Easy Wind
It would take them a while to work out the time changes!
11/1/69 - Uncle John's Band instrumental
11/8/69 (Dick's Picks 16) had the first Cumberland Blues, which needed a bit more practice....
The first one on the Archive is from 11/15/69 -
12/4/69 - Black Peter, Uncle John's Band with lyrics
12/19/69 - Mason's Children
A song they decided not to release, though they recorded a studio demo in Feb '70.
12/20/69 - New Speedway Boogie
The chorus singing is, um, quite different.
3/20/70 - Friend of the Devil
http://www.archive.org/details/gd1970-03-20.sbd.smith.99182.sbeok.flac16 (with some alternate lyrics)
We're lucky to have a tape of the original Dawson/Hunter recording of Friend of the Devil too! (from fall '69) -
(This tape also has the Dead working out the Uncle John's instrumental.)
4/3/70 - Candyman
5/14/70 - Attics of My Life
Some of these early versions show the Dead struggling with it....
6/7/70 - Sugar Magnolia
Needed some more work!
7/30/70 - To Lay Me Down
Also, a unique Dead studio version recorded that summer was released on the So Many Roads box set.
8/18/70 - Truckin', Ripple, Brokedown Palace, Operator
Truckin' is acoustic, with Pigpen on piano. The first '70s show with multiple song debuts; they were recording American Beauty that month.
9/17/70 - Box of Rain
Our only Box of Rain from 1970. According to Deadlists, Pigpen's on piano, Jerry's on pedal steel, and someone's on fiddle, but frankly it's nearly inaudible.
9/18/70 - Till The Morning Comes
This song never changed much. More well-known versions came on 10/4 and 10/31/70.
Bertha & Bird Song were played at the 12/16/70 Matrix rehearsals with David Crosby, and Loser was played (with fiddle!) at the PERRO sessions in January '71, but they're not on the Archive.
Jan/Feb 1971 - Playin' in the Band, Bird Song, Greatest Story Ever Told, Wharf Rat (studio rehearsals)
2/18/71 - Bertha, Loser, Greatest Story, Wharf Rat, Playin' in the Band
Famous show of course, with five new song debuts. Along with the August '70 shows, this show marks a change in the Dead's pattern: instead of dropping songs into the sets one-by-one when composed, now they tended to write a whole bunch of songs in a touring break and introduce them all at once. Two new songs were left for the next night...
2/19/71 - Bird Song, Deal
7/31/71 - Sugaree, Mr. Charlie
8/24/71 (Dick's Picks 35) - Brown Eyed Women, Empty Pages
10/19/71 - Tennessee Jed, Jack Straw, Mexicali Blues, Comes A Time (with an extra verse), One More Saturday Night, Ramble On Rose
Six debuts. Clearly they had a busy month off!
12/31/71 - Chinatown Shuffle
3/5/72 - Black Throated Wind
Weir's solo album "Ace" had been recorded a month earlier.
3/21/72 - Looks Like Rain, Two Souls in Communion
http://www.archive.org/details/gd1972-03-21.sbd.miller.92395.sbeok.flac16 (with Pedal steel)
4/17/72 - He's Gone
Quick & snappy.
6/17/72 - Stella Blue
http://www.archive.org/details/gd72-06-17.aud.hanno.16470.sbeok.shnf (fair AUD) - with Pigpen on organ.
7/16/72 - Mississippi Half-Step
http://www.archive.org/details/gd72-07-16.sbd-aud.cotsman.11258.sbeok.shnf (poor AUD)
(The next performance is more listenable - http://www.archive.org/details/gd1972-07-18.sbd.miller.32878.flac16 )
2/9/73 - Row Jimmy, Loose Lucy, Here Comes Sunshine, They Love Each Other, Eyes of the World, China Doll, Wave That Flag (early version of U.S. Blues)
Another one of the famed "let's debut a whole new album" shows, with seven new songs. Only three of these songs would make it onto Wake of the Flood, though, which was recorded in August '73.
9/7/73 - Let It Grow
9/8/73 - Weather Report Suite, Let Me Sing Your Blues Away
The Weather Report Suite is tricky - the Prelude had been floating around for years, Let It Grow debuted on 9/7/73, and the whole Suite was first performed on 9/8. Another of the few Dead songs that debuted only after being recorded for an album. (Let Me Sing Your Blues Away turned out to be more short-lived.)
http://www.archive.org/iathreads/post-view.php?id=263203 - list of early Preludes in '72/'73.
http://www.archive.org/details/gd69-04-05.sbd.miller.18701.sbesok.shnf - the earliest Prelude tease I've found. (There's also a tease in the 8/6/71 Other One reprise.)
The first performances of the remaining Mars Hotel songs (recorded in April '74) aren't too distinctive:
2/22/74 - Ship of Fools, It Must Have Been the Roses, U.S. Blues
3/23/74 - Scarlet Begonias, Cassidy
Cassidy was a very belated debut from Weir's "Ace" album.
April 1974 - studio rehearsals
Listed here since the first three performances (Pride of Cucamonga, Money Money, & Unbroken Chain) are "live in the studio," and two of those would never see the stage that year.
5/17/74 - Money Money
http://www.archive.org/details/gd1974-05-17.sbd.miller.89972.sbeok.flac16 (first of three)
6/23/74 - Let It Rock
OK, it's a cover and not a Dead song, but worth mentioning as the only Dead performance of a song off Garcia's Compliments album. This show also has the debut of Seastones!
From early '75, of course, we have innumerable rehearsals of the new songs in the studio, but to focus on the live debuts:
3/23/75 has the first of three Blues for Allah>Stronger Than Dirt performances.
6/17/75 - Help On The Way (no vocals)>Slipknot>Franklin's Tower, Crazy Fingers
(An early Slipknot riff had also been played a few times in '74 jams, for instance 2/22, 6/20 and 7/25/74.)
8/13/75 has a rare Sage & Spirit (the only other one was on 10/31/80).
8/13/75 also had the first live Music Never Stopped, but the first live one on the Archive is from 9/28/75 - http://www.archive.org/details/gd75-09-28.sbd.fink.9392.sbeok.shnf
6/3/76 - The Wheel, Might As Well, Lazy Lightning>Supplication, Dancing in the Street (disco version), Samson & Delilah
After the hiatus, a new Dead style emerged. Here the Wheel finally surfaced live, five years after being recorded! Dancing in the Streets (which had been in the sets from 1966-1970) was radically rearranged; They Love Each Other and Friend of the Devil (played 6/4/76) were also in new slowed-down renditions.
6/4/76 - Mission in the Rain
Not a Dead song really, but the first of five Dead performances of this song.
6/28/76 - Happiness is Drumming
A precursor to Fire on the Mountain. The Dead also teased this in Playin' in the Band jams that year (like 6/22/76), and Garcia had played it live with the Diga Rhythm Band on 5/30/75.
2/26/77 - Terrapin Station, Estimated Prophet
(Although I should note, an early Estimated Prophet riff was being practiced as early as '74!
3/18/77 - Fire on the Mountain
Mickey Hart had done a studio version of this with Garcia a few years earlier:
5/1/77 - Sunrise
(I had omitted this song from the list earlier; but no one ever mentioned it...)
5/15/77 - Passenger
Well, that's as far as I'll go with this....
Another interesting list could be made of the first performances of the Dead's covers - for instance, to take a random few from Skull & Roses, the first versions of Not Fade Away, Goin' Down the Road, Big Railroad Blues, Me & My Uncle, and Mama Tried are rather different than what they became. I'm putting together that list as well....