Ok well all pages linked to from my home page get listed higher on google. Why is that? To me it seems because PR on home page is higher then where the other pages get linked from even though i have 0 pr because its a new site im expecting it to be more (those who say PR means nothing please comment on this). i have a huge site about 20 million pages, main page links to 40 categories who link to 45 subcategories who link to about 300 sub sub categories who then link to the content that really needs the higher SERP but being so many pages i cant link to them from the main page, the few i did have on the main page i removed and 3 days later they moved down on SERP about 10 results. getting links from other sites to my deep pages comes to mind but for that i would need thousands... wouldent it be the same if i just get my home page to say pr6 and that makes all sub pages pr5 who then make the other pr4, well you get the point.
I will suggest you to work on quality !!! Just remember not to make your website look like a Link farm as you have so many pages ... keep the links on the home page limited and wait .. you will automatically notice changes ... i think building links for categories and sub-categories will be great ... but dont go for directory submitting at this point .. go for some good quality relevant links !!!
I have experience the same situation that you have described...but I need to admit that my website has approx 100 pages not 20M .
Ok, of course you have a very large website, but your website should be optimized very carefully. As you said, you have given so many links on home page. keep number of links on home page limited. Monitor traffic on the pages of the web sites and try to find top pages which has drawn maximum traffic,fix top 100 or 200 pages and then promote these pages to the great extent, do deep linking from these pages to the deep pages and try to draw pr and traffic to the inner pages. This is the best way to optimize the large website when you can't optimize so many pages simultaneously......
Try to keep only main links in home page otherwise your site will look really messy and may loose potential customers
place only few main links on home page.... placing to many links will make it look like a links farm and you may loose potential customers..