Как сделать, чтобы функция начала работать с итераторами?
Не надо кушать лишней памяти, и лишний раз ходить по итератору тоже.
def all_unique(iterator):
    counter = 0
    items = set()
    for item in iterator:
        items.add(item)
        counter += 1
        if len(items) != counter:
            return False
    return True
Худший случай, конечно, всегда один для данной задачи: О(N) и по памяти, и по времени. Но в лучшем случае может хватить всего лишь 2 итерации цикла и множества из 1 элемента (это когда в итераторе 2 первых элемента уже одинаковые), а в среднем будет что-нибудь типа O(N/2).
Может, содержимое итератора высыпать в список и потом обрабатывать?