Iced Earth - Everything has been said.
Dio (+ Dio-era Black Sabbath) - Ronnie James Dio (RIP) is one of the greatest figures in heavy metal history.
Helloween - There is a very broad Maiden/Helloween fan overlap. Personally, I have little use for them, but I am certainly and definitely in the minority. If you like them, check out the related bands, Gamma Ray and Iron Savior.
Blind Guardian - In case you are into fantasy, Blind Guardian is the thing for you. I am not into fantasy, but I still enjoy them very much. With their latter albums, they got rather "technical", as opposed to their very speed oriented early years and their very bombast ways in the mid-nineties.
Metallica - Almost a no-brainer, but their early to mid-eighties albums are quite close to Maiden when it comes to compositions and musical vision.
Megadeth - Similar to Metallica, but their early nineties and post-2001 work will certainly appeal to any Maiden fan, I guarantee it.
Running Wild - More on the "power" side of things (whatever that may mean), and very much bombast-oriented, but their late eighties and early nineties work is as close to Maiden as anything of that time will ever be.
Judas Priest - Again, a no-brainer, but look beyond their clichéd image of the "quintessential" heavy metal band and explore their depths.
Saxon - I personally think they got very boring and repetitive with their post-Crusader albums (the only essential song on that album being the title track), but their first few albums will tell you a lot about where Maiden came from.
Angel Witch - Their eponymous debut is an essential heavy metal album. This was what Maiden had to put up with in their early days.
Grave Digger - I have figured that this band is all about the choruses and has little substance otherwise. The choruses are great, with an exceptional sense of melody, but for everything else, the singer's German accent may put you off.
Accept - A matter of taste. They are something of a cross breed between the Scorpions and AC/DC.
Sabaton - A fairly young band that takes a lot of inspiration from the East End gang, but be warned - they are rather cheesy.
Annihilator - Dubbed a "technical" thrash metal band, you can tell they are very heavily influenced by Maiden.
W.A.S.P. - If you have a thing for eighties cheese, this might be the band for you. Even if not, they have a very unique sound that is however very "heavy metal" in the eighties sense, and instantly recognisable.
Queensryche - The originators of progressive metal, though I just can't see why. I always felt "progressive metal" is overlong and boring musical wankery, while the 'Ryche are exciting and catchy. Definitely a must, especially for their masterpiece, "Operation: Mindcrime".
Manowar - Don't let people who say they are stupid and ridiculous put you off. Musically, this band was brilliant during the eighties, even if you have to put your mind off their lyrics here and there. If you like Maiden at their more epic, you may enjoy them too. I certainly do.
This should keep you occupied for some time.