Q:

Where, sequentially, do Interfaces sit in an introduction to Objects?

I've been teaching Objects for years now as part of AP Computer Science A (which means that I am teaching OOP in Java), and I have experimented with putting Interfaces in at different locations.  In general, I currently teach in the following order:

Class Structure: the coupling of data with relevant methods.
Information Hiding: making each class responsible to guarantee the integrity of its data.
Designing the API: Given what we've learned, how should we design the public face of our classes?  Included in this section is the concept of overloading.
Inheritance: Creating relationships among classes, inheriting and overriding.
Polymorphism: Being able to utilize children in place of their parents, and how that works.

Interfaces seem most related to Polymorphism to me, since we can (for instance) make an ArrayList<SomeInterface> but wherever I put it in, it always feels like some add-on instead of like the core and vital concept that it really is.
Where (and how) do you integrate Interfaces into your OOP exposition?

A:

Ideally, interfaces come first. Before Classes. Interfaces define concepts. Classes implement those concepts. Don't think of them as an add-on to OO programming. Think of them as the essence. 
In fact, if you present a pre built class to students, my guess is that you already, probably informally, give the interface first. Here is a class with public methods "accept" and "spitOut", or something like that. You probably talk about the public methods first and the necessary parameters and return values. More importantly, you probably talk about the intent of the class and of the individual methods. Most likely, and I think most common, only then do you discuss the implementation of the methods along with fields, etc. 
If you start your discussion with the fields, on the other hand, you are (IMO) making a big mistake and that students will start out by thinking at too low a level and will write their code too often in terms of getters and setters. In other words the encapsulation will be inconsequential and possibly leaky. Then, in a program with a few tens of classes and a few hundreds of objects, but, perhaps thousands of fields, they will be thinking about the fields and how they mutate, rather than the concepts represented by the objects in the system. Their thinking will be at a lower level than is efficient (or even possible, in some complex programs). 
But if you introduce the concepts first, and get them to (a) think in terms of those concepts and (b) implement those concepts faithfully they will be naturally led to think at a higher level of abstraction, which is really what programming languages are for in the first place. 
Some rules that I'd adhere to with rare exceptions and no exceptions at the start. 

When you implement an interface don't give the class any additional public methods. Thoroughly document the intention of the interface and its methods.
When you build a subclass of an existing concrete class, don't give the subclass any public methods that don't have signatures in the superclass. (Abstract classes can be a bit different, but it is dangerous and adding public methods should be delayed.)
If you need new things in a subclass, extend the interface instead, as it represents a new concept, and implement that, rather than just extending the superclass, though you can also extend as an implementation strategy. 
Prefer composition of objects over inheritance. An object is composed of other simpler objects (representing their own concepts). With composition you will probably be able to 
  
  
a. Write simple classes (a few public methods)
    b. having simple methods. I get antsy when a method is more than about 4 lines or has any nested internal structure. 

Use simple design patterns to make it fit together. These are just another sort of concept and are themselves normally defined with interfaces.  
Avoid getters and setters (in interfaces and classes). They lead the student to think of everything in terms of mutations of implementation, rather than at a high level. I use accessor for a method that returns information (possibly a field's value, but not always or often), and mutator for a method that somehow changes the internal state of an object. A mutator might in fact have nothing to do with fields and might pass on a message to one of the implementing objects or set up a chain of mutations. Thinking in terms of setters is too narrow, but also too low level. 
  
  

Some modern OO languages don't have formal interfaces, but you can normally simulate them to separate out the ideas from the implementations. 

Note that the Standard Template Library (which I haven't used in quite a while) was, itself defined in terms of concepts and the term was (maybe still is) used in the literature. This was just a placeholder for interfaces that C++ didn't support. 
The idea here is to build a software system in terms of readily understood concepts. The resulting system has its complexity in the interactions of simply understood things, rather than in the things themselves. 

Note that I often write an interface when I intend only one implementing class. Capture the concept first. 
Again, note that I often write an abstract class that has protocol (abstract methods) for every method in any intended subclass. This lets me capture a common implementation, but keeps my concept clear as I subclass. I never need to ask instanceof and I never need to cast an object reference. Everything naturally fits together freeing my mind to think of other (higher level) things. 

