King Diamond - Welcome Home
and / or
Mercyful Fate - Dead Again (cuz its sorta symphonic)
Cradle of Filth - She Mourns a Lengthening Shadow (instrumental)
Some kinda John Williams Medly - Star Wars, ET, Superman, etc...
If they're gonna do Genesis, its gotta be Tonight, Tonight, Tonight, I can hear Russel "I'm comin down, comin down like a Monkey! But it's all right!"
I'll second the Trogdor by Strong Bad request.
Judas Priest - Painkiller, see if they can topple Death's cover of that one
Judas Priest - Exciter
Rush - Subdivisions
YJM - Heaven Tonight or Teaser
A Video Game Medly - Castlevania, Metroid, Megaman, Ninja Gaiden, etc or more Modern - Diablo, Starcraft, etc.
Bon Jovi - Bad Medicine
Megadeth - Last Rites / Loved to Deth
Metal Church - The Hitman
and last but, yeah, well I guess least too
Tupac - My Last Wordz