Good move. Highly recommended for many reasons.
>> 2. Moved any bulk navigation code below the unique content using the rowspan technique. <<
Might be useful. Using includes for this code can make your site admin a tad easier too (no SEO effect).
>> 3. Created images for any repetitive content such as addresses etc. <<
I really can't see Google penalising for a repeated address. Anyway you need that detail in text on at least a few pages of the site otherwise you'll never rank for your own address.
>> 4. Removed sitewide "comment tags" caused by using templates or othewise. <<
Comment tags are ignored for indexing and ranking. They might be scanned as an indicator of spam. If you only had a few tags per page then I see no difference in removing them; especially if they make the developers work more difficult.
>> 5. Removed calls to offsite tracking codes. <<
I can't see what that would achieve, at all.
>> 6. Randomly changed the names of "common" images within the site. <<
Why? Extra work for no gain, and maybe some loss. If you refer to a file that has a particular size but it appears on your site under 50 different filenames, Google might think you were trying to pull some stunt using keywords as file names. Bad move. By using the same filename for the file on every page, as most people already do, the file is cached and saves you bandwidth: the file is then served once per visitor, not once per page view. This random-name change is a backwards step. I wouldn't do it that way at all. You're clutching at straws here.
>> 7. Changed the navigation based upon the category of the page. <<
Sounds fair enough. If the new system is useful to visitors and bots alike, then no complaints.
>> 8. Removed the "alts".
An image tag is NOT valid HTML if the alt is missing. The minimum allowed is alt="". The alt text is used for accessibility reasons. Put them back, only adding text for important content images and for navigation images. For other images use the minimal alt="" instead.