In some ways it is saner than Clojure btw ...
For example Clojure devs pride themselves that their language doesn't have variables, but oh wait, it has Vars and function definitions must be dereferenced on call sites and those Vars can be modified wherever, whenever, as Clojure does not have the notion of "val" or "final". And of course you can do thread-local bindings for those Vars and that's why people have used it for things such as dependency injection, as a poor man's implicit arguments that do not appear in the function's signature. I don't even know if those persistent data-structures could be implemented in Clojure, as you need final's semantics for that and Clojure's data-structures are actually implemented in Java.
I also like Clojure's protocols a lot, but they've got limitations as compared to type-classes from Haskell or Scala. For example in LISP lazy by-name parameters are modeled by means of macros, which is OK, but then if you want a macro as part of an interface, tough luck (this is a LISP vs ML thing). Protocols aren't doing interface inheritance either. For example in Scalaz (a Scala library bringing in many goodies from Haskell) the Monoid type-class inherits the interface of Semigroup, because a Monoid really is a Semigroup, I don't think anybody can argue against it and it isn't "complecting" anything.
The process of learning Clojure has been very frustrating for me. I get it that the language doesn't have loops, I don't do loops in Scala either, but the absence of loops is the least interesting part of going functional - absence of local mutable state is not solving a big problem. The more interesting part for which I found little guidance is for modeling changes (in user input, or the various data sources that we use). In Scala we use more and more concepts and design patterns coming from Haskell, whereas I found Clojure to be maybe a little too pragmatic for my taste - for example Clojure devs aren't modeling Monads, a fact that is apparent starting with the standard "map", "filter" and "mapcat", builtin functions that work only on the builtin collections; Clojure doesn't even have some kind of Numeric protocol for building your own things that work with the numeric operators; and I hate things like the sorted-set using java.util.Comparable (what's up with the lack of abstractions in the standard library btw?).
Of course I could go on - and I'm sure Clojure developers will jump to rectify me - Clojure has a lot of cool things in it and that's why I keep on learning, because some day I might have an aha moment, plus everybody should learn a LISP, just like everybody should learn a functional statically typed language (be it Haskell, Ocaml or Scala).
I like how pragmatic Clojure is, but I think I can understand when you said that it's "maybe a little too pragmatic". The more I learn about Haskell (which is still very little, to be honest), the more I wish that Clojure had more in common with Haskell. On the other hand, the new work on transducers to me seems to solve some of the problems that you bring up about map, filter, etc., in that transducers work with any manner of data sources and sinks.
For example I like how Clojure people are doing what they call "light-weight data modeling". In Scala and Haskell we get too focused on types, sometimes we go overboard, forgetting that the data should stay reasonably decoupled from short-term business needs.
So there's something really refreshing about Clojure's approach (which is in general LISP's approach to doing stuff). On the other hand I really like having a potent compiler that can help me deal with accidental complexity, which is why people will never agree on which is better, because it depends a lot on context (i.e. the kind of problems you're working on).
You could implement the persistent data structures even in C. Being persistent is a matter of API, not implementation. But actually, Clojure's deftype creates immutable fields by default, so you do get the Java like final semantics (that is, you can't set the fields even though they are public).
The main reason why protocols differ from interfaces in Java or type classes in Haskell is because Clojure is a dynamically typed language. Protocol inheritance would have very little value as knowing that a monad is a functor is quite useless if you don't even know if something is a monad.
Macros don't really need polymorphism. The macro can always expand to a polymorphic function call or it can pass the s-expression to a polymorphic function.
You can actually implement the sequence interface for your own types too. But it is unfortunate that it is an interface, not a protocol, and the documentation for implementing it is nowhere to be found. What is available are functor and monad abstractions, in the contrib library.