1. You can add methods to other people's types.
2. My solution is not incomplete. It solves the stated problem exactly. If you need to sort the objects with a different criteria, implement the interface with whichever criteria you want. It's not so difficult. Generics will not save you from having to implement some kind of comparison criteria in other languages.
3. You can add more methods to the interface for an out of place sort.
4. If you need to implement a b-tree, add the methods to whichever type you need to sort appropriately.
It's not that big of a problem. You will not have to up and down cast. You only have to cast a type of interface{} to your type once and only once while you are comparing.
Is your problem ideological or specific to this example?