As far as albums go:
Dream Theater - Scenes from a Memory
Ayreon - The Human Equation (my favorite album ever)
Ayreon - Into the Electric Castle
Ayreon - Universal Migrator
Queensryche - Operation Mindcrime (only part 1, part 2 is worthless)
Blind Guardian - Nightfall in Middle Earth
Trans-Siberian Orchestra - Christmas Eve and Other Stories
Trans-Siberian Orchestra - Beethoven's Last Night
Not yet mentioned:
Shadow Gallery - Tyranny/Room V...put together, it's a fantastic 2.5 hour prog metal story.
Aina - Metal Opera (it's, like, a metal opera)
Emperor - Prometheus: The Discipline of Fire and Demise (if you like black metal)
Lots of good songs mentioned already, but also:
Iced Earth - Gettysburg: The Devil to Pay, Hold at All Costs, & High Water Mark (classic/power metal, 3 parts, 30 minutes total, you will probably learn more about Gettysburg in this song than you did in history class)
Nile - In Their Darkened Shrines (death metal, 4 parts)
It's funny how about 7 of my favorite 10 albums are concept albums.