Re: Progressive Rock (sixties / seventies / eighties)
The Gods Of Prog Rock, Part the First...
Yes
They were among the first real prog bands - those who played prog full-time, instead of merely influencing the genre (e.g. the Beatles were at times very proggy, but they weren't a prog band). They also became the biggest, and the definitive band for the symphonic prog subgenre. After two somewhat interesting albums, they got Steve Howe on guitar and produced the phenomenal The Yes Album. They were at their peak for the next two albums, when they had Rick Wakeman on keys: Fragile and Close To The Edge. Anyone who doesn't know those 3 albums doesn't know prog.
Genesis
They weren't quite as successful as some other Gods Of Prog here, but their influence has perhaps been greater than any other band's ... it's impossible to conceive of Marillion if there had not been Genesis first. The essential albums are Foxtrot and Selling England By The Pound, but (like Shadow said) anything from Nursery Cryme to Wind And Wuthering excels. Despite their reputation of "going pop" in the 80s, they never abandoned prog - although they took its sound in a pop direction as well. Check out 80s Genesis prog classics "Home By The Sea / Second Home By The Sea", "Domino" and "Driving The Last Spike".
Pink Floyd
I don't think much needs to be said about Floyd, as they're so well known. Their space-rock sound has had a massive impact on later prog bands, especially Ayreon and Dream Theater. To really appreciate the Floyd, I've found it's good to listen to all the albums in order, starting from The Piper At The Gates Of Dawn. You can hear how parts of their style/sound were there from the start, while other parts developed over time. Sure, that's true with many bands, but I think Floyd is an exceptionally dramatic case.
King Crimson
These guys can get extremely weird at times and took me a long time to get into. They're almost impossible to categorize, due to both avant-garde leanings and diversity of style/sound. Yet they were a big part of this scene. Original singer Greg Lake went on to ELP, and later Bill Bruford (drums) came over from Yes after that band made Close To The Edge. I like the Red and Larks' Tongues albums the best, but your taste may differ.
Emerson, Lake and Palmer
Keith Emerson is a freaking inhuman GOD on keyboards. Palmer's great, even Lake has his moments, but the reason to listen to ELP is for Emerson. Brain Salad Surgery is their best album, with "Karn Evil 9" standing as their magnum opus (with honorable mention to "Tarkus"). The real tragedy: Jimi Hendrix was going to join this band, met with ELP and everything was planned out, but died before it happened. HELP would have been mind-blowing.
Jethro Tull
Their greatest accomplishment was supposed to be a joke! They tried to make a parody of all the prog rock albums with their side-long epics. In the process they nearly outdid all the other bands here, since Thick As A Brick is one of the greatest prog albums ever. They kept more blues in their sound than most other prog bands and had a notable folksy leaning too.
Camel
If you like Genesis, you'll like Camel. Their sounds have some similarities, though Camel had a substantial jazz influence. (Prog that swings!) Their first three albums are fantastic. The best place to start is with Mirage, which contains the epic "Lady Fantasy". Their first (self-titled) album has some really grooving instrumental parts, especially the song "Six Ate". Their third (all-instrumental) album, Music Inspired By The Snow Goose is a good mellow listen.
Have you noticed a trend here? All of the above Gods Of Prog are British. I'll post about some American prog in Part the Second...