How about this one, though:
PyDict_NEW(int) => PySetObject * PyDict_ADD(s, value)
ADD would just stick value in the next empty slot (and steal its reference).
Dicts, sets and frozenset are implemented as hash tables, not as arrays, so the above suggestion doesn't make any sense to me. The location of the "next empty slot" depends on a the key associated with the value being added (btw, where is the "key" handled in your proposed API?). Consequently, the PyDict_New(int) step would have no way to know where to create the n empty slots (since their location is determined by the hash value of the keys). That is a reason that the tuple/list API differs from the set/frozenet/dict API.