Remember ... people first ...
How are the conversion rates from the site? Is it performing well for those visitors who manage to find it?
Determine what is working well before you gut the fish. You don't want to go backwards just for the sake of some search engine theory.
Once you've got a handle on what people like about the site, try to work around that without impacting it too much. For example, I'd see where I could minimize the use of images without changing anything about the look and feel. Often, an image map can be 'sliced' and you can then use CSS or a simple table to position the must-have images around what used to be the text content of the big image. Heck, slicing a big image is a good idea, anyway, as it improves the perception of the site's loading speed. Use the 'longdesc', 'alt' and 'title' properties in each IMG tag. While it's true that most SEs don't pay any attention unless the image is linked, some do, and more are starting to pay attention to 'longdesc' as time goes on.
OWG had some good advice about site map links and Karri is correct about the 'alt' property, but it's not all about the SEs, and the 'alt' tag is still used by browsers like Lynx, among other non-graphical programs.
while a site map assists with the technical aspects of spidering, it doesn't really describe the site structure in terms of page importance iyswim the way that you would want ppl to view it
Well ... it depends on the site map, I suppose. If you simply list each page, you're right ... no indication of importance and little indication of structure. The site map can be as informative as you'd like to make it, and doesn't need to be a 'traditional' site map at all. Take a look at the 'concept map' .. er .. concept
from the IHMC (and maybe try their free tool). In that case, you end up with a type of image map, too, but it's easy enough to include the text-link version on the page, as well.
To sum up: Start by seeing what's working, try not to mess with it's forumla for success, but clean out the deadwood and tighten down the hatches, then work on revamping less-than-terrific features ... then start working on optimizing whatever content there is.