Water
Maiden has a lot of songs that have more or less to do with water, so I think it would make a perfect thematic setlist, especially since it wasn't given appropriate portion in The Legacy of the Beast Show. I'm sure this is already planned out; it's the only logical explanation for the fact that they haven't played all these gems live for ages (if at all)! They wanted to do these songs justice and wait for a right moment. You'll see!
The stage would be, obviously, the standard Maiden stage set with waves and stuff painted all around the drapes. Bruce's stage clothing would consist of different swimsuits, from Speedos to a full wetsuit and stuff like raincoats and pea coats and some kind of a military outfit for those positioned in submarines during World War II! Instead of very cliché swords and flamethrowers and that kind of stuff Bruce would wield an umbrella and scuba diving equipment. Nicko's teddy bear would wear diving equipment as well and Nicko himself would wear snorkel.
1. Rainmaker (w/ giant inflatable umbrella, rain effects)
2. Sea of Madness (it's metaphorical, but I guess it counts)
3. Ghost of the Navigator
4. Lightning Strikes Twice (w/ handheld umbrella)
--
5. The Talisman (w/ rotten food, rats and whatever on stage)
6. Run Silent, Run Deep (w/ inflatable submarine on stage)
7. When the River Runs Deep (see "2. Sea of Madness)
8. Still Life (there's a pool in this one - it must be played!)
9. Isle of Avalon (it has several mentions of rain, lakes, sea, water and all that sure - they'll play it for sure!)
--
10. Flight of Icarus (he fell into the sea, didn't he?)
11. Rime of the Ancient Mariner
12. Fear of the Dark
13. Iron Maiden
--
14. Alexander the Great ("BY THE AEGEAN SEA..." - finally, they will play it, I'm sure! What a perfect opportunity to finally play this masterpiece live!)
15. Wasted Years
16. Hallowed be thy Name
Invasion isn't here, even though it's story has a lot to do with ships and stuff, but I think they will never play that one.