It's easily rationalized, but you might not guess it from the documentation.
Indeed the same thing happens in Java:
(get (java.util.TreeMap. {"a" 1}) :a)
A sorted map obviously involves a comparator, but the documentation of sorted-map does not say what kind of comparator you get if you don't specify. You may tell from the stack trace that the exception emanated from the default comparator, which is compare.
(compare "a" :a)
which is described at https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/compare. It is an expedient default because the host's object system participates, but Java's Comparable requires compatible arguments.
In brief, you can either provide your own (more accommodating) comparator to sorted-map-by, or guard the lookups. Your own comparator can be any two-argument function, so it is easy to do, but will incur the expense of a type check more often than guarding your lookups.
