Our data structures book with C++ (Data Abstraction and Problem Solving with C++: Walls and Mirrors 7th ed.) covers and uses templates from the beginning. We do so in a simple straightforward way. The code that we present enables a student to create a data structure that stores data of any one data type (all strings, all Car objects, and so on). As we state in the book, "Templates enable the programmer to separate the functionality of an implementation from the type of data used in the class." We feel that introducing and using templates as we do is not difficult.
Code that creates the same kinds of data structures as just described and that does not use templates is inflexible, since it is hardwired for one particular data type. Changing the type of data to be stored would be an error-prone process and take a substantial amount of work. Such code would not look like the code that a student is likely to see in the standard libraries or in the real world.