My vote is to keep the flat list format you already have. In my past experience with Algorithm::Diff, I've found the output from diff a little too deeply nested to be, er, easy to use. If anyone prefers that format, they can use the existing interface.

I keep thinking it would be nice to show empty ranges with (undef, undef), but I can't think of a situation, other than eyeballing the data, where $aMin < $aMax wouldn't also work.

It took me a few seconds to realize what you were doing with @diff[2-5, 4-5]. Would it be easier to build the list backwards (with unshift), then reverse it before returning? (OT: Actually, I liked the 2-5 trick. I think I'll start using it myself....)

These are just minor nitpicks. Overall, this is a very nice piece of work. I'll probably start using it even before the patch hits CPAN. As for a name, I suggest context, because it reminds me of diff -c.