Here is a debugger feature that I think I would find really useful: avoid stopping at any given location more than once. This would be particularly useful when finding my around an unfamiliar bit of code - it would step into a function that I hadn't stepped into before, and then step over it the next time it was called, for example. In fact, I often find myself trying to do exactly this, just remembering which functions I've stepped into before (and often getting it wrong).
The other use case for this feature would be doing a sanity test once some new code has been written - the debugger would just stop on the new/changed lines of code so that you can make sure that they're working as expected.
One difficult part about this feature (especially for the second use case) would be keeping track of which locations have been stopped at even across recompiles (so the instruction pointer location won't necessarily be the same) and across source changes (so the source line location won't necessarily be the same either). So really to implement this properly we need to completely overhaul the entire compilation system so that it takes as input the deltas from the last compilation and performs the corresponding modifications to the output files (including both the binary and the list of which locations have been visited).
Such an overhaul would be extremely difficult, but would be useful for other reasons as well - in particular, it has the potential to make builds much faster, which shortens the edit/recompile/test sequence and makes programming much more pleasant. Also, it could integrate with editor syntax highlighting and code completion features, so that these always reflect the current state of the program.
I'd think it would be a pretty effective compromise to use stack traces to refer to chunks of code--it would decrease the granularity of your "have I seen this" queries, but in general a function body refers to a single semantic chunk of code, which is the right level of abstraction for becoming familiar with new programs. This obviously wouldn't be effective in hand-assembled code or some programs written in higher-level languages, but seems like it would provide most of the benefit with only a small portion of the work as compared with some sort of heuristic to determine which lines of assembled output have changed since previous versions. That said, if such a system is actually what you want, I'd wonder if Google's work with their Chrome update system is applicable to this sort of endeavor: to shrink the sizes of their binary diffs, since they know the diffed file is executable code, special handling for e.g. modified jump addresses based on added/removed code elsewhere in the binary lets them produce a much smaller and simpler diff that closer approximates a source diff in "shape". That involves determining which parts of the code are generated from the same source lines as those in an older binary, &c., some of the same problems that crop up here.