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.