Many of our students do indeed think (functional programming/programming in Haskell) is difficult. They learn many concepts/ideas (e.g. recursion, algebraic data types, higher-order functions, type inference, equational reasoning, typeclasses, some IO/monadic programming) that are new/different to them. There is simply a lot to learn, and hence they think this is difficult. I can sympathize with that. (By the way: I never claimed FP/haskell was easy to teach: since there is a lot to learn, so there is a lot to cover in a relatively short time; that sometimes makes it challenging).
However, I don’t particularly see why they should find the notion of a Foldable typeclass so strange/difficult. If you can accept that there is a “Num” typeclass that expresses that there are types that look like numbers (and thus provides functions to work with such things) then is it really all that surprising that there is a “Foldable” typeclass that models “container-like types” with functions that allow you to combine/flatten/reduce the container into some value? The hard part is actually explaining the idea of a fold (i.e. a higher order function), not so much that you can define something like fold/foldr/foldMap for Lists as well as some other data structure.
Of course there are some weird instances for Foldable. We don’t explicitly spend time on those, and in all likelyhood our students will not try to use any of those instances themselves throughout the course (either since they don’t need them to to solve their homework questions, or since they don’t fully realize that they could have (attempted) to use these instances). Whether they will hit those issues later I don’t know, but at least I don’t think it is a “beginner” issue.
In all honesty; issues in terms of tooling (e.g. getting a working compiler, editor etc) are much more challenging to deal with as a teacher: if students have an frustrating start it is difficult to motivate them afterwards. Moreover, it is time consuming to help students to get something to work, since every time it is a different puzzle you have to solve to figure out what is wrong. Luckily things have improved quite a bit in the last few years, and I hope they will continue to do so in the future :).