The generics thing turns out to not really be a problem. Yes, writing 100% Abstract Data Types is unsatisfying. However, when I'm actually writing custom data structures, I generally have an interface that I want to use because I want the data structure to take advantage of a peculiarity of the data being stored.

But, you know, bad for a teaching language.