The instrumental interplays, I think. Especially the tradeoffs. It's a "later day" song but Judgement Day's instrumental is Purpulesque in my ears. From early days, Revelations.
But the most DP-alike song should be Stranger in a Strange Land, for the riff and the hammond textures.
You're right, though, that the influence is not straight forward, however the Sabbath influence is even less obvious. For me.
Maiden in that sense doesn't sound like anyone, they're their own thing. They have a lot of influences, mostly from progressive rock genre, but from the big "1st wave" metal trio, I get that Deep Purple feel a lot, just an attitude towards instrumentals and jamming expressed through the end product. I know Dickinson said that Maiden not being 100% certain about jams and extended instrumentals in the 1980s was one of his exit factors. He also notes that 21st century Maiden does this and that's why it's "better". That reads that tendencies were always there.
I can hear some Sabbath here and there and some Zeppelin here and there, but it's inside discrete songs. Like COTD and Innocent Exile. Overall, Maiden's dependence on pure riff and slow groove is small, love songs are almost nonexistent and there's no sex factor involved. From that viewpoint, they have largest similarity with DP inside those big 3.
In the end, as GhostOfCain says, prog rock is the bulk of the influence, UFO, P.Gabriel Genesis, PF, The Who, Beckett, harmonies were inspired by Wishbone Ash and Thin Lizzy, etc. These details are quite known.
