> max and min for a range object are already O(1) one-liners:

true; dropping

> As for __and__, it doesn't feel like a particularly natural operation to me, given that a range object represents an *ordered* sequence of integers rather than just a subset.

True, there is no canonical sorting. However, the concept of the intersection of ordered sets is commonplace and implemented in other libraries, for example:

http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%27A.17%27,swi%28%27/doc/Manual/ordsets.html%27%29%29

http://hackage.haskell.org/packages/archive/containers/0.4.1.0/doc/html/Data-Set.html#v:intersection

http://hackage.haskell.org/packages/archive/data-ordlist/0.2/doc/html/Data-List-Ordered.html#v:isect

My implementation inherets the ordering of the first range:

R(1) R(2) R(F)
p    p    p
n    p    n
p    n    p
n    n    n
key: p === positive === increasing
key: n === negative === decreasing

Haskell documentation has an apt paradigm for the ordering: "Elements of the result come from the first set"; similary my implementation selects elements from the first set common to the second.

From a programming persepctive this is quite natural too:
lcm = (a*b)/gcd(a,b)
where lcm determines the ordering. Basically, the behavior of the attached __and__ implementation is driven by python's gcd function.