Two worthy finalists. Both sound like there is thought behind them, while they also are excellent examples of each guitarist's distinctive style. In addition, both are further enhanced by the interaction with the bass line. Finally, both fit very nicely to the atmosphere of the respective songs they are part of.
If I were to select a handful of Maiden solos that I would listen to over and over again, these two would be there, no doubt.
But now that I must choose one to vote for ... Stranger. In addition to being a damn fine piece of guitar work on its own, it is a great example of music that can help create images. During that first part, I can almost imagine standing alone in the ice, staring towards the horizon ... no brave new world.