set's don't have values, and you are wanting to implement the partial ordering based on the values.  (side-note: how does partial-ordering work for sets?)

> That is, one counter will be considered smaller-or-equal to another if for any
> item in the first counter, the second counter has an equal or bigger amount of
> that item.

According to your definition, my example should have returned True, which is clearly nonsensical.

Even if you changed the definition to:

  For every item in the first counter, that item's value is less than the
  corresponding item in the second counter.

You have situations like:

  Counter({'a':1, 'b':1}) < Counter({'a':2})

I just don't think there is one interpretation that is going to be correct most of the time.