tedster - 6:24 am on Apr 21, 2010 (gmt 0)
On-site, I'd also consider a strong "themed" architecture [webmasterworld.com], with little to no cross-linking between the individual. Internal linking should be in the vertical direction.
Also avoid the thin or "stump" pages that plague large database sites. You're going to need a lot of backlinks to get Google to index anything near to 1,000,000 URLs anyway, so don't start out with your hopes that big.
For link building, I'd aim to create highly useful, and even novel, content for the main "hub" pages at the top of the themes and sub-themes.