THe sitemap doesn't need to be at the top necessarily, but I think it still helps. Make sure it is linked from the homepage, that way the spiders can find it and will be able to access all of your "important" pages. I think it does help with indexing the pages.
I have seen no difference in indexing based on location of the site map. As far as site design, though, the only reason for a visitor to use the site map is if your main navigation is so confusing the only way to get around is to look at a map.
Take a look at your site, is the navigation easily accessible and clearly organized? Do your links allow spiders to index your site? Do you have every part of your site included in the navigation? If so, then you don't even need a site map (but it doesn't hurt to have one anyway). If not, then I'd focus on fixing your navigation: it's much more important for real users to find their way around your site than for spiders.