A Site Map can be a useful 'secondary navigation' tool, especially as a site grows and becomes more complex. Sometimes the completeness of a well organized Site Map can be very helpful to your users. A customized search feature which will return the results that you want the user to find can also be very useful.
Don't know that the mods will allow specific Site Map links, though some good examples would be extremely beneficial as most Site Maps are garbage - hindering the user experience and chasing them off the sites. Terrible Site Maps are a rampant weakness. Use this to your advantage. Organization and layout are crucial.
Many search applications (essentially another method of finding what we want, and not all that different in function from a Site Map in some respects) are also garbage because they do not filter to the pages that a user is most likely looking for. If I search for - widget x - and the search returns 100 or more result pages - I am gone.
Keywords, link architecture (blah, blah, blah) - If the map is telling your visitors what each page is (what they should expect to find if clicking that link), then the keywords are already there and the SEs will scoop them up just fine. Design for the USER. Build it - and the SEs will follow. If it is easy to find categories, sub-categories, and so forth right down to specific pages - then you have a good, useful design. (Link architecture is just a $20.00 phrase for useful design:)) Nothing more than the old fashioned 'outline' - general heading, sub-heading, group, sub-group, and so forth - drilling down the site from the most general home page, to the most specific product image page.
BTW - The on-site Site Map does not have to include absolutely every page that exists on the domain. It is a tool to help direct your users, and sometimes it is best to leave out a lot of the 'insignificant' pages. They will find them from the landing pages if need be.
IMO - Two Site Maps are better than one. I regularly give Google an updated sitemap.xml - following the protocols and being as complete as possible. What I give Google, Google loves. What I give the user, the user loves - and Google doesn't seem to mind that both sitemap.xml and sitemap.html are provided.
The XML page is not a public page. But you may want to keep it private from those that might have an interest in having it. Plenty of people just use www.example.com/sitemap.xml - which hands your competitors your entire map, plus the weight that you have assigned certain pages over others. Bury it somewhere and just give Google the correct address.
sitemaps.org is a good place to check out. Also, read Google's own pages and their Webmaster Tools are also good to check out. There a lot of Site Map generators and some are a lot better than others. Free tools can be okay, but not a bad area to spend money on better tools!