Surprisingly, I'm not tired of any Maiden song. Sometimes I am, of songs like RTTH, The Trooper etc, and I skip them, but the very next time I start banging to them like never before.
Besides, if RTTH and NOTB are everything they ever play of Maiden in Metal bars... (OK, to be fair, they had Wasted Years two weeks ago, and I virtually infected everybody with my air guitar energy back then).