Justified `instanceof`? Using it with an interface but not an implementation type

When a code contains the Java instanceof operator, many people will raise their eyebrows and say it is a no-no. For example, in this other SO Q&A, the answer said:

Note that if you have to use that operator very often it is generally a hint that your design has some flaws. So in a well designed application you should have to use that operator as little as possible (of course there are exceptions to that general rule).

However, it does not further elaborate when the use of instanceof is okay, and when it is not.

I put some thinking on this, and articlate the following guideline. I thought this may have been discussed somewhere on the Internet, but I could not find it. Hence this question and asking for your comment:

Using instanceof on an interface is okay; using instanceof on an implementation is not okay

Here is an example on the "okay" case (I think there have been a lot of discussion on the "not okay" case so I am skipping it here).

Example: A catalog of animals, some (but not all) of them can fly

Animal.java

public interface Animal {
    String getName();
    String makeNoise();
}

CanFly.java

public interface CanFly {
    float getMaxInAirDistanceKm();
}

Cat.java

public class Cat implements Animal {
    @Override
    public String getName() {
        return "Cat";
    }

    @Override
    public String makeNoise() {
        return "meow";
    }
}

BaldEgale.java

public class BaldEagle implements Animal, CanFly {
    @Override
    public String getName() {
        return "BaldEagle";
    }

    @Override
    public String makeNoise() {
        return "whistle";
    }

    @Override
    public float getMaxInAirDistanceKm() {
        return 50;
    }
}

Catalog.java

import java.util.ArrayList;
import java.util.List;

public class Catalog {
    private List<Animal> animals = new ArrayList<>();

    public void putAnimal(Animal animal) {
        animals.add(animal);
    }

    public void showList() {
        animals.forEach(animal -> {
            StringBuilder sb = new StringBuilder();
            sb.append(animal.getName() + ": ");
            sb.append(animal.makeNoise() + " ");
            if (animal instanceof CanFly) {
                sb.append(String.format(" (can stay in air for %s km)",
                        ((CanFly) animal).getMaxInAirDistanceKm()));
            }
            System.out.println(sb.toString());
        });
    }

    public static void main(String[] args){

        Catalog catalog = new Catalog();
        Cat cat = new Cat();
        BaldEagle baldEagle = new BaldEagle();
        catalog.putAnimal(cat);
        catalog.putAnimal(baldEagle);

        catalog.showList();
    }
}

Test Output

Cat: meow 
BaldEagle: whistle  (can stay in air for 50.0 km)