How do I do a case-insensitive string sort in a language-insensitive manner?

You need to use a new Comparator, not the default Comparable. The String class comes with a special Comparator you can use: String.CASE_INSENSITIVE_ORDER.