First of all, interfaces do not have any performance benefit. In any case, the use of polymorphic code and dynamic dispatching (for example, C ++ virtual functions) carries a cost.
Think of interfaces not as adding expressive power, but as something that makes it difficult for you to write. Interfaces are important, IMHO, for three reasons:
1) They can help you write code with better encapsulation, data hiding, stability, etc.
2) They can help you separate behavior and implementation by thinking about what you are trying to imagine, rather than how to implement it. The inability to add state does a lot so you cannot accidentally add it.
3) They allow you to expand things in the future and separate your code from independent units. Each component knows only what it needs to know about other services.
You can do some of this with abstract classes that have no state, but interfaces are specifically designed for this and carry the benefits of multiple subtyping. In C ++, such abstract classes are often used to mimic interfaces.
Now, if you can write a huge system with an ideal level of encapsulation directly with classes, this is great. But with classes, it is often tempting to prematurely make a fortune and create connections.
Should you always write interfaces? Of course not. Always be afraid of the "Always" rules :) This is always a balance between wasteful work and useless complexity and advantages. With time and experience you get the instinct for this.
In addition, the header files are essentially interface files. Usually they determine acceptable behavior, but not state. If you learn C and then Java (some schools do), you will learn about ADT in C and then about ADT in Java using interfaces.