I’m not sure how generally useful this is, but if you need it, it may be close to what you need. PreviousNextInCategory is a plugin that adds two container tags, <MTEntryPreviousInCategory> and <MTEntryNextInCategory> that work just like the <MTEntryPrevious> and <MTEntryNext> tags, except that they give you the previous and next entries that are in the same category as the primary category of the current entry.
Which is where things can get a little weird: if you have a previous entry that has the primary category Food, but the secondary category Sex, then as you browse backward through Sex entries, when you hit that Food entry (because it’s also Sex), you’ll suddenly switch over to browsing Food instead of Sex. So it’s probably most useful for something like the original problem, where you only have a few distinct categories, or for people like me who rarely remember to add more than one category.
In any case, I’ll probably leave it doubled up with the by-date links on my archives until I get tired of seeing it. One other thing it might be good for, displayed the way I have it: it encourages you to write about a variety of things, since it looks rather stupid when the previous and next entries by category are also the previous and next entries by date, giving you two lines of the exact same links.