Let's take case (a) -- that's the approach I adopted when implementing a Splay tree, introducing a Comparator interface. Granted it is a bit of a pain to write IntComparator, LongComparator, etc., but given that Go is not an object oriented language e.g. all types do not support a (hypothetical) CompareTo(other T), it is not clear to me how would the availability of generics would help in this case.
For basic type coercion, yes, it is a pita to write boxing code, and clearly a maintenance issue as well.
The simplest way that they would help your example is by ensuring that you can't add a mix of ints and strings to the same splay tree. Presumably this would cause a runtime failure. Generics add type safety.
For basic type coercion, yes, it is a pita to write boxing code, and clearly a maintenance issue as well.