Priest certainly is.. the definition of (dumbed down, cliched, generic, cheesy) metal, but Maiden is more than that. Their first two albums have a huge punk rock influence. They also released two hard rock albums (fotd, npftd). They have 70's classic rock songs (angel & gambler) There are many other songs I can think of that have more of a non-metal sound than your typical metal band. Two examples: Flight of Icarus, Dejavu. Things like that are enough to make them a classic rock band in my book.
You don't know what a noob is.