chaosapiant
Ancient Marinade
Starblind and Avalon don’t have as many changing parts as the songs you mentioned, but the parts that are there are unusual time signatures and much more complex on a playing level. A lot of Maiden songs switch tempos and riffs all over the place but generally stay in 4/4. I have no idea wtf time signature Starblind is but it sounds like a bitch for six people to play live.To me, Dance Of Death, Paschendale, When The Wild Wind Blows, and The Red And The Black all feel more complex than Isle Of Avalon and Starblind and those were all played live.
I don't think I ever see snippets available ahead of time for any new album releases these days. The last Maiden album to have those was Final Frontier.