TravisBickle

Since you’re a Maiden fan you might like some older stuff such as Fates Warning’s “Awaken the Guardian” and “The Spectre Within”, Satan’s “Court In the Act”, Helloween’s “Keeper Of the Seven Keys” albums and Queensryche’s earlier material.
Mercyful Fate and King Diamond’s “solo” work as well though the high pitched falsetto vocals are a hit or miss for most people. I think he’s one of the all time best.
For newer stuff maybe Iced Earth, they have an awful lot of Maiden influence.

And for something totally random try checking out Viking metal-era Bathory albums, “Hammerheart”, “Twilight of the Gods”, “Blood On Ice” and Nordland 1 and 2.
Look up epic in the dictionary and you should see Quorthon’s name.

Unknown Soldier

A lot of good recommendations here especially with Fates Warning being mentioned (Ray Alder great vocalist) If you like the Maiden influence as in Iced Earth check out Nevermore as well, another great band that fits in nicely to the more centric traditional metal territory.