Помогите не запутаться с итератором

Тут дело не в итераторе, а в понимании концепции интерфейсов. По сути своей интерфейс - это особый вид классов, который описывает не схему конкретного типа объектов, как это делают другие классы; интерфейс - это по сути своей контракт, который говорит, что объект любого класса, который будет реализовывать этот интерфейс, будет иметь реализацию методов этого интерфейса. Самый простой пример, который приходит в голову - это Съедобное / Несъедобное. Ты описываешь интерфейс Съедобное и говоришь, что любое съедобное будет иметь метод taste() (попробовать), который возвращать объект типа Вкус:

public interface Edable {

    Taste taste();
}

enum Taste {
    SOUR, SWEET, BITTER, SALTY;
}

Ты не можешь создать объект интерфейса, это значит что ты не можешь создать просто какое-то съедобное, ты можешь создать класс Лимон или класс Жареная картошка, которые будут реализовывать этот интерфейс, и возвращать объект типа Taste:

class Lemon implements Edable {

    public Taste taste() {
        return Taste.BITTER;
    }
}

public static void main(String[] args) {
    Edable lemon = new Lemon();
    System.out.println(lemon.taste());
}

И ты можешь создавать объект типа Lemon и помещать её в переменную типа Edable, потому что в использовании этого объекта тебе неважно, лимон это или картошка, тебе нужно только знать, что это что-то съедобное, а значит, у него можно узнать вкус (вызвать метод taste()). Так и с итератором. Тебе в целом неважно, что именно там за итератор лежит. Тебе нужно только знать, что он умеет перебирать элементы коллекции и возвращать очередной элемент методом next().

List или Map - это тоже интерфейс, но тебя же не смущает, когда ты пишешь

List<String> list = new ArrayList<>();

"Нельзя создавать объект интерфейса" - это означает, что нельзя создать объект, не реализовав все методы, объявленные в этом интерфейсе. То есть нельзя написать так:

List<String> list = new List<String>();

Поэтому нужно либо выбрать конкретную реализацию этого интерфейса (ArrayList, LinkedList), либо сделать свой анонимный класс и создать его инстанс этого класса:

List<String> list = new List<String>() {
    // implementation add, remove, ...
};

То есть ты создаёшь конкретную реализацию интерфейса List и помещаешь её в переменную более общего типа List. Теперь к итератору

Set<String> strings = new HashSet(Arrays.asList("alpha", "bravo", "charlie"));
Iterator<String> iterator = strings.iterator();

Здесь ты не создаёшь объект итератора напрямую, через new. Вместо этого ты вызываешь метод, возвращающий некую реализацию интерфейса итератор. То есть в интерфейсе Set объявлен метод iterator(), возвращающий объект, реализующий интерфейс Iterator, и это гарантирует, что у всех реализаций интерфейса Set, в частности у HashSet, будет своя реализация этого метода. В частности у HashSet возвращается итератор типа HashMap.KeyIterator, он и содержится в переменной типа Iterator.