I generally like coding things to interfaces, as you often implement the interface twice; once for the real system, once for unit tests of other dependent components. Not using interfaces leads to either compiling test code into your production binary, or other more-horrifying hacks (mocks!).
I read a few great articles on this a long time ago and unfortunately I don't have the references at hand, but it was compelling enough that I Interface anything that's going to be proxied or injected.
That being said, I REFUSE to call anything an Impl. If I have an interface called FileSavingService, I'll have a LocalFileSavingService or an S3FileSavingService, but I'll chop my fingers off before I add Impl to the end of them.