Dependency Injection: Turtles all the way down?

The examples you provide do not use Dependency Injection. Instead, Bar should use Constructor Injection to get a Foo instance, but there's no point in injecting a concrete class. Instead, you should extract an interface from Foo (let's call it IFoo) and inject that into Bar:

public class Bar
{
    private IFoo f;

    public Bar(IFoo f)
    {
        this.f = f;
    }

    public int doSomethingWithFoo
    {
        int x = this.f.doSomethingWithExternalDependency();
        // Do some more stuff ...
        return result;
    }
}

This enables you to always decouple consumers and dependencies.

Yes, there will still be a place where you must compose the entire application's object graph. We call this place the Composition Root. It's a application infrastructure component, so you don't need to unit test it.

In most cases you should consider using a DI Container for that part, and then apply the Register Resolve Release pattern.

Keep in mind the difference between unit testing and integration testing. In the former, the dependency would be mocked whereby it provides expected behavior for the purpose of testing the class which consumes the dependency. In the latter, an actual instance of the dependency is initialized to see if the whole thing works end-to-end.

In order to use Dependency Injection, your classes would have their dependencies injected into them (several ways to do that - constructor injection, property injection) and would not instantiate them themselves, as you do in your examples.

Additionally, one would extract the interface of each dependency to help with testability and use the interface instead of an implementation type as the dependency.

class Foo
{
    private IExternalDependency ed;
    public int doSomethingWithExternalDependency() {...}

    public Foo(IExternalDependency extdep)
    {
      ed = extdep;
    }
}

What most people do is use a mocking framework to mock the dependencies when testing.

You can mock any object that the class under test depends on (including behavior and return values) - pass the mocks to the class as its dependencies.

This allows you to test the class without relying on the behavior of its (implemented) dependencies.

In some cases, you may want to use fakes or stubs instead of a mocking framework. See this article by Martin Fowler about the differences.

As for getting all the dependencies, all the way down - one uses an IoC container. This is a registry of all of the dependencies in your system and understands how to instantiate each and every class with its dependencies.