Hi Will,
Personally, I approach this from two perspectives: Usability and SEO.
Usability: I don't think I've ever clicked on a footer sitemap myself when looking for things on a website. If organic search does not take me to what I want, I do a bit more browsing with a last ditch effort using the keyword search box. If that doesn't work, I bounce back to my organic search results and try another site or refine my search.
Therefore, I removed the footer sitemap from our ecommerce site and created a left nav link to additional categories. The link is above the fold and I call it "Additional Categories." I am shocked at the volume of visitors who go to that page - far more than every visited our footer sitemap.
SEO: In my opinion, a sitemap moves links up to the second tier click level because they are buried too deep and don't get the juice. These pages need to be moved up perhaps because the link structure and hierarchy are not sound or maybe it is just too big of a challenge to flatten out all portions of a site.
Therefore, I flatten out and improve the link structure (or as sound as you can get). If there are categories that warrant indexing, but are not best sellers, I put them on the additional categories page. If some of the categories are 3 clicks (sometimes 4) and difficult to flatten out or fix, I put them in the additional categories page so people can see them and spiders can crawl them. Our site currently does not have the authority to force the juice to deeper penetration.

