Right here. [!--emo&
--][img src=\'style_emoticons/[#EMO_DIR#]/biggrin.gif\' border=\'0\' style=\'vertical-align:middle\' alt=\'biggrin.gif\' /][!--endemo--]
Flight of Icarus is probably the easiest Maiden song (for everybody except the singer, there are some high notes in there). The Prisoner and Wasted Years are also easy.
The songs you mentioned:
2 Minutes To Midnight and The Wicker Man are fairly easy, but the rhythm guitar parts are slightly harder than the songs I mentioned above. Hallowed is going to be rough on the lesser guitarist. You'd probably have to ask him to play only chords, and just have one guitar playing the melody lines.
The biggest questions you should ask yourself are:
Is every band member committed to learning the song before the rehearsal?
If the answer is yes, all these songs (except maybe Hallowed) should be something you can nail down as a band within one hour. If you're in a situation like my band, where sometimes our lives are too busy to practice individually between jam sessions, you may need 2 hours or more.
How many rehearsals will you have before the gig?
If you have 2, tape your band at the first rehearsal. Then you can hear on the tape what needs the most work, and try to get it right the next time. It always sounds better (in your mind, at least) when you're playing it, so rely on a tape to hear the truth.
What's your audience like?
It's always more fun to play something that the audience enjoys. If it's not strictly a metal/hard rock audience, then I'd stay away from Hallowed or 2 Minutes. I've had the experience of perfectly performing obscure metal songs only to have the non-metal audience collectively not care at all, and it really is a drag. (And yes, Hallowed is obscure to non-metal audiences.)
If you're playing at a bar, remember that drunk audiences don't have a discerning ear - you can get away with an imperfect performance, which gives you more freedom to experiment.
Then again, Maiden got where they are by playing what they wanted and not giving a damn if it pleased the crowd or not. (Fortunately, it did and then some.) So just make sure you like what you're playing. If you have fun, the audience will follow.