Just my two cents...
Google was indexing my site pretty well until I submitted a sitemap. Then, not only did my indexing stop - also my traffic died off almost completely - all my rankings tanked. No idea why.

My opinion is that Google can find your pages just fine without a sitemap as long as you have a logical structure to your site. I would build links to your top and sub level categories using social bookmarking etc. Also, on page links (in modules etc) to your lower level categories will help alot.