Мне кажется, вы уже знаете, какие у вас есть варианты, но вас просто не устраивает ни один из их. Вот мой взгляд на три варианта, которые вы предоставили:
Функциональная Java - этот вариант кажется вам наиболее подходящим. Он соответствует всем вашим требованиям, за исключением того, что вам не нравится документация. С моей точки зрения, документация выглядит простой, но работоспособной. Их фрагменты кода должны помочь вам быстро приступить к работе. Кривая обучения кажется почти несуществующей, что должно помочь смягчить недостаток документации. К вашему сведению, ядро Java TreeMap также основано на красно-черном дереве.
Scala - Это выбор, который я бы сделал, если бы был на вашем месте. Кажется, вы не хотите изучать новый язык, но Scala - это очень простой переход с Java. Вы можете сначала написать код, очень похожий на java, и постепенно усвоить более функциональные идиомы. Взаимодействие Java <-> Scala также превосходно в обоих направлениях.
Clojure - Как бы я ни любил Clojure, его сложно рекомендовать в данном конкретном случае из-за радикально другого синтаксиса и крутой кривой обучения для java-разработчика.