I'm not certain this is true in general. I would argue that whatever you learn first is what you consider "intuitive". Ask people who went to schools that started in Scheme/Racket who hadn't done any programming before, and I expect they will tell you that they find immutability and recursion to be completely intuitive. Indeed, they might find other approaches less intuitive.

Other than the comment about performance, the "disadvantages" you list for functional all seem to stem from the fact that most people aren't introduced to it early. Note that people who learn pure procedural programming first often find OO to be intimidating and unintuitive. We are all most comfortable with the things we understand and feel uncomfortable learning new things that are different.