Alex: good point - thanks!
Attaching updated version of the patch (again, against py3k, likewise, I'm somewhat new to this code, so I may have missed things)
With this:
>>> dis.dis(lambda o: o in {1,2,3})
1 0 LOAD_FAST 0 (o)
3 LOAD_CONST 3 (frozenset({1, 2, 3}))
6 COMPARE_OP 6 (in)
9 RETURN_VALUE
>>> dis.dis(lambda o: o in {1,2,3,3,2,1})
1 0 LOAD_FAST 0 (o)
3 LOAD_CONST 3 (frozenset({1, 2, 3}))
6 COMPARE_OP 6 (in)
9 RETURN_VALUE
and the tuple/list cases are again as in the original comment.
I'm in the process of running the full test suite.