Search engines aren't stupid. Except on very rare occasions (which are usually fixed soon after), they always think through and test any algorithm changes carefully. The situation you described is not a corner case or even a minority case. That's a situation that occurs on most web hosts and websites. So naturally Google/Bing/Yahoo aren't going to penalize you just for that.
If it doesn't make sense (ie. doesn't improve search results for the user) to penalize websites for sharing IP addresses or treat shared hosting sites differently from sites on dedicated servers, then the search engines aren't going to do it. Why would they?
Likewise, duplicate content penalties are to prevent search results from containing redundant pages (which is completely useless to users) and to discourage spammers and like-minded webmasters from generating large volumes of pages to flood the search index.
It's perfectly natural for a site to have keywords which show up on multiple pages. If your site is about Rottweilers, then of course "Rottweiler" is going to show up a bunch of times on different pages all over your website. So why would Google or Bing punish a webmaster for that sort of repetition? The people who work at Google/Bing/etc. are smart enough to look at how much content two pages have in common before labeling them as duplicates. Just because they have 5-6 words in common out of 200-300 words doesn't mean they're duplicate content. Likewise, they know to take shared navigation menus and header and footer content into account.
The only thing you need to be concerned with is whether the design of your site is useful to the end user. Is the repetition of your name on 78 pages good design (ie. does it add value for the user?), or is it just needless repetition from poor site architecture?