The biggest problem with getting into the earlier Doctor Who stories is that there is no DVD box set of (most) seasons.
I'll start by linking to Wikipedia which has a full list of all stories available on DVD, and shall pick out some of the most important ones.
The first two doctors have many missing stories, which exist only in audio form, with some still images. These are (I believe) available legally for free (because the teams who created the "restored" versions are only allowed to distribute them for free).
Thus there are many early Doctor Who stories which will probably never again see the light of day, since they're unlikely to be rebroadcast, or to be released on DVD.
However, most of the "big" episodes from the earlier doctors are available on DVD. These are normally episodes which featured some major villain, like the Daleks or Cybermen.
Like David Thomas, I'd recommend "The Beginning" DVD, mostly for historical reasons. Early first Doctor is interesting for knowing the origins of the show, but he's almost unrecognisable even compared to the later first doctor episodes.
As for other First Doctor stories, I'd honestly wait off on them until you know you like the style of the earliest Doctor Who stories. Second to Fourth doctors are much more "beginner friendly".
Second Doctor has a few "key" stories which I'd highly recommend.
Tomb of the Cybermen features the Cybermen, and is a great story The Cybermen were first introduced in a first doctor story which no longer exists in its entirety, but this is one of their earliest appearances.
The Invasion is another Cybermen story, featuring the Cybermen on earth, and is the first story with missing parts to be released on DVD, with the 2 of 8 missing episodes released on the DVD as animations.
The War Games was the final Second Doctor story; and was the first story to mention or show the Time Lords. I'd recommend this one very highly, as it's a great (10-part) story which features the first major details about the Doctor's past.
Third Doctor and onwards have more DVD releases, simply due to the fact that all episodes from here on still exist in some format.
I'd recommend a few stories here:
Doctor Who and the Silurians, Terror of the Autons, and The Three Doctors to name a few.
The Fourth Doctor is easily most people's favourite Doctor. Almost any Tom Baker story you pick up will be an excellent watch. Some highlights:
The Key to Time (a whole season with an ongoing plot arc), Genesis of the Daleks (a bit of a retcon compared to earlier 1st and 2nd doctor stories, but one of the best Dalek stories), City of Death, and the "New Beginnings" DVD set, containing Keeper of Traken, Logopolis (Fourth Doctor's death) and Castrovalva (first Fifth Doctor story).
Those are what I'd call the highlights of the first four doctors, and any of them would be great to pick up and get into Classic Doctor Who!