I do SEO for a site even larger. Getting the longtail indexed is my main priority... ranking for shorthead pages and competitive keywords is my secondary initiative. However - I am far more successful at that.
Flowing link juice from the more powerful pages to the lower pages is one of the main issues. I can't tell you what the best way to go is. I have three different "systems" set up and don't know myself which works best. Recently did a relaunch and I am now waiting for that to stabilize. I hope to have some conclusive data within the next three to six months.
One tip I will give you - which I have been able to solidly confirm - is that if you need more than 5 clicks from your main page to the "last" page you won't get those pages in the index. I try never to go further than 4 clicks out. Finding the ideal solution to categorizing and spreading your content to achieve that - if you have that many pages - and following the "no more than 100 links"-rule (in order to not dilute link power too much) is going to be a key challenge.