On one of my newer sites, I've put the entire site menu on the lower half of the page. I know if it was on top it would be more visible to spiders, but these are pretty much the only text links on the site. The upper part consists of an h1 tag, couple of dynamic links within the site (nofollow) & 468*60 google ads. Now these pages are indexed..so I'm not complaining. Any advice?
I think you shouldnt worry too much about it. Many sites don't have Search Engine friendly navigation, other use images instead of text links for internal navigation. IMO, whatever you are doing is alright and shouldnt give any problems.
The spider sees things that are on the upper part of a page "better" or earlier... This is how a spider "sees".
Why the hell do you want spider to see your internal links better or earlier than your real keyword-rich content? Sooner or later, the spiders will follow all the links they find on your page. The only problem would be if your page´s content exceed the spider´s limit for fetching (e.g. spider´s limit is 100KB, your page has 120 KB and links are in the not fetched 20 KB). Forget about internal links, rather use this "better or earlier viewed" portion of your pages for content that will drive you new visitors. If you want better ranking for your sub-pages, just manage some deep links with relevant anchor text from other domains to those pages directly
There isn't much keyword rich content on the homepage, just a download link... The keyword rich content is in the interior pages.
It wouldn't make a lot of difference under normal circumstances (pages of normal length). If it were to be a factor, it will be considered having very minimal impact then your title and header tags.