Converting from service-locator to dependency injection

I'm the process of cleaning up some code. I have decided to do this because it is very likely that new features will be requested in the near future and the code is hard to grok (not only because it uses a dependency container as a service locator).

To a fair extent, I understand why SL is terrible for dependency management and I've declared all dependencies of a method in the operation's signature even before I knew what OOP is.

When working with frameworks like AngularJS, you get dependency injection for free. This is not the case with my current project. The only way I can think of instantiating the application "the right way" is by service-locating everything in the main method. Please point me in the right direction toward a more elegant implementation of dependency injection.

This is my idea:

sub main()
    container = new Dic
    container->set(A, lazyNew(foo/bar/A)
    container->set(B, lazyNew(A))
    container->set(App, lazyNew(App), depends-on:[ A, B])
    // more configuration code
    app = container->get(App)
    app.main()

The flaw here is that I'm still using the container as a service locator. The only benefit is that the dependency graph is "resolved automatically" (tedious configuration and declaration of dependencies for every instance). Another pro is that instantiation happens in one place. Please help me understand how to take this to the next level of awesome.