Some potential strategies:
¬†¬†¬†¬†Google Webmaster Tools allows you to request an increased crawl rate. Try doing that if you haven't already.
¬†¬†¬†¬†Take another look at your navigation architecture to see if you can't improve access to more of your content. Look at it from a user's perspective: If it's hard for a user to find a specific piece of information, it may be hard for search engines as well.
¬†¬†¬†¬†Make sure you don't have duplicate content because of inconsistent URL parameters or improper use of slashes. By eliminating duplicate content, you cut down on the time Googlebot spends crawling something it has already indexed.
¬†¬†¬†¬†Use related content links and in-site linking within your content whenever possible.
¬†¬†¬†¬†Randomize some of your links. A sidebar with random internal content is a great pattern to use.
¬†¬†¬†¬†Use dates and other microformats.
¬†¬†¬†¬†Use RSS feeds wherever possible. RSS feeds will function much the same as a sitemap (in fact, Webmaster Tools allows you to submit a feed as a sitemap).
¬†¬†¬†¬†Regarding sitemaps, see this question.
¬†¬†¬†¬†Find ways to get external links to your content. This may accelerate the process of it getting indexed. If it's appropriate to the type of content, making it easy to share socially or through email will help with this.
¬†¬†¬†¬†Provide an API to incentivize use of your data and external links to your data. You can have an attribution link as a requirement to the data use.
¬†¬†¬†¬†Embrace the community. If you reach out to the right people in the right way, you'll get external links via blogs and Twitter.
¬†¬†¬†¬†Look for ways to create a community around your data. Find a way to make it social. API's, mashups, social widgets all help, but so do a blog, community showcases, forums, and gaming mechanics (also, see this video).
¬†¬†¬†¬†Prioritize which content you have indexed. With that much data, not all of it is going to be absolutely vital. Make a strategic decision as to what content is most important, e.g., it will be most popular, it has the best chance at ROI, it will be the most useful, etc. and make sure that that content is indexed first.
¬†¬†¬†¬†Do a detailed analysis of what your competitor is doing to get their content indexed. Look at their site architecture, their navigation, their external links, etc.
Finally, I should say this. SEO and indexing are only small parts to running a business site. Don't lose focus on ROI for the sake of SEO. Even if you have a lot of traffic from Google, it doesn't matter if you can't convert it. SEO is important, but it needs to be kept in perspective.