Yeah, big sites have their own challenges, that's for sure. The place to start for any site is to define your purpose and what market[s] you hope to serve. From there on, with 1 million pages, I definitely hire a true professional in IA - like someone with a library sciences degree who is also web savvy.
There's an interesting large site IA project going on right now - with public blogging so we can play along at home: Istockphoto. They've produced some interesting video:
iStock F5: Information Architecture [youtube.com]
F5 Redesign - New Design [youtube.com]
The first video shows just how dramatic the change in IA is going to be.