I believe that some basic concepts like the ones of category and functor could be taught since first courses of algebra, that's because these concepts are not more abstract than those of groups-group homomorphism,ring-ring homomorphism, vector space-linear map which are taught in the first year's courses. Categories and functors can be easily shown to a young public respectively as graphs with structure (i.e. operationoperations) and as graph morphisms preserving the structure. Many example can be given to those concepts which can be understood by undergraduates: the categories of graphs' points and graphs' paths, the category of sets and functions, the category of groups and group homomorphisms, vectorial spaces and linear maps, but also monoids, groups and poset as categories. Another good set of examples of category the are quite easy to understand and (in my personal opinion cool) are those of objects (which can be molecules, automaton's states, dynamic system states,...) and processes transforming one object into another. These examples are pretty cool because they open the way to application of category theory also to other science, besides giving really concrete examples of categories.
Last motivations of teaching category theory early is that many times seeing thing from an abstract point of view helps when we want to switch constructions from categories, where these constructions are build naturally, to other categories (it comes to my mind the example of homotopies of complexes in homological algebra) and also shows deep unity of lots of mathematical objects that maybe at first seem unrelated.
Before to end I would also like to add some motivation to why not waiting to teach category theory in advanced courses: if you do so usually happens that these categorical concepts are presented in very fast way that make difficult to take familiarity with said concepts and that doesn't allow to deeply understand the meaning and usefulness of categorical results.
One last comment: I don't know why but every time I think to those people which consider category theory too abstract and useless they remind me of what Kronecker said about Cantor, and this make me smile.