##Addendum##
I just noticed your intro paragraphs could use some addressing too. You sardonically say that IoC containers "aren’t employing some secret technique we’ve never heard of" to avoid messy, duplication-prone code to build a dependency graph. And you're quite right, what they're doing is actually addressing these things with the same basic techniques as we programmers always do.
Let me talk you through a hypothetical scenario. You, as a programmer, put together a large application, and at the entry point, where you're constructing your object graph, you notice you have quite messy code. There are quite a few classes that are used again and again, and every time you build one of those you have to build the whole chain of dependencies under them again. Plus you find you don't have any expressive way of declaring or controlling the lifecycle of dependencies, except with custom code for each one. Your code is unstructured and full of repetition. This is the messiness you talk about in your intro paragraph.
So first, you start to refactor a bit- where some repeated code is structured enough you pull it out into helper methods, and so on. But then you start to think- is this a problem that I could perhaps tackle in a general sense, one that isn't specific to this particular project but could help you in all your future projects?
So you sit down, and think about it, and decide that there should be a class that can resolve dependencies. And you sketch out what public methods it would need:
void Bind(Type interfaceType, Type concreteType, bool singleton);
T Resolve<T>();
Bind says "where you see a constructor argument of type interfaceType, pass in an instance of concreteType". The additional singleton parameter says whether to use the same instance of concreteType each time, or always make a new one.
Resolve will simply try to construct T with any constructor it can find whose arguments are all of types which have previously been bound. It can also call itself recursively to resolve the dependencies all the way down. If it can't resolve an instance because not everything has been bound, it throws an exception.
You can try implementing this yourself, and you'll find you need a bit of reflection, and some caching for the bindings where singleton is true, but certainly nothing drastic or horrifying. And once you're done- voila, you have the core of your very own IoC container! Is it really that scary? The only real difference between this and Ninject or StructureMap or Castle Windsor or whatever one you prefer is that those have a lot more functionality to cover the (many!) use cases where this basic version wouldn't be sufficient. But at its heart, what you have there is the essence of an IoC container.
