Best settings for xml sitemap, cron time and submission time?
The indexing you are having is moderate / typical indeed. Only a small percentage of sites (from the 100% existing in the web right now) are being indexed every hour or so (some sites are indexed once smaller times like 20 minutes or even less - Wikipedia for example could be indexed in 10 minutes or less in some cases).

You should use various Drupal modules to raise the both PageRank and PQS (Page quality score) of your sites pages. 

Use wisely the modules MetaTag, AdvAgg, xml sitemap, pathauto, search404, redirect and others to insure you achieve that targets. 

More ways to handle that many 404's - Either your could redirect all the nodes to the homepage or groups of them to some nodes with suitable context).  Moreover, if you have the spare timenergy or resources you could make redirects to NID's 1x1 for all or most of your links. You could also delete some via WMT and than via robots.txt. It is recommended by some to make redirects not in Drupal but rather directly in the main .htaccess file for better performance.