Okay, I've definitely convinced myself there is no good way to do this without having to write way too much code over and over again. The problem is basically equivalent to inserting items into a sorted list, but you only have one operation in which to do it. So, you are either limited to simple types, or your code for operations on types explodes trying to define all of the ways to compare types (in a generic sense) and different scenarios for combinations of types.
This requires a Turing-complete type system.