I'm developing an an app which uses the Google distance matrix, the directions service and some map-features like custom markers. Where would you put all this different functionality? Inside of a controller, a service, a directive or even a module with combination of them? What would be the most angular way to do so in your opinion?
All manipulations with DOM in Angular should be done through directives. It's the "angular way". There is an angular-ui project that have Google map example.
Look at theirs google map directive code.