I disagree. I think interfaces can be a powerful way to think about what you want to do without having to focus too much on how it will be done, compartmentalise that 'part' and then move on to something else.

Not necessarily until there are 3 implementations existing, since by that time it could be difficult to factor out the interface, but I think it's at the time that you very clearly see that there will be at least 3 implementations. The problem you want to avoid is creating interfaces for generality when you don't see a clear need for it yet.