I like the idea of "programming to interfaces" and avoiding the use of the "new" keyword.
However, what do I do when I have two classes that have the same interface but are fundamentally different to set up. Without going into detail about my specific code, I have an interface with a method, "DoStuff". Two classes implement this interface. One is very simple and requires no initialisation to speak of. The other has five different variables that need to be set up. When combined, they allow for literally millions of ways for the class to work when DoStuff is called.
So when do I "new" these classes? I though about using factories but I don't think they are suitable in this case because of the vast difference in setup. (BTW: there are actually about ten different classes using the interface, each allowing the formation of part of a complex pipeline and each with different configuration requirements).