Why isn't Functional Programming Taught First?
The why isn't necessarily related to the relative quality or benefit of the various approaches to the first courses. But some of the comments given to the question capture part of the reasons. 

First, FP isn't precisely mainstream in industry. Most programming in the real world is now is done in Dijkstra-derived languages, not McCarthy-derived ones. This may change, of course, as the world starts to recognize the benefits of FP as it previously did for OOP. As the questioner mentioned FP has advantages in some important areas. But most curricula take a look at who is hiring entry level folks and what they want to see in the person's background. 

Another reason is that most of the faculty is much more knowledgeable about those mainstream things than others. If the faculty went through a long program in which almost everything is built in Dijkstra-derived languages that is what they are more likely to teach beginners. OTOH, faculty (including some folks here) who went to, just to pick a name, MIT, are more likely to start in FP, but may still be constrained by the first reason. 

Most faculty still think of FP as an advanced topic and so Let and Lambda tend to come late in the curriculum, after the students have seasoning. As you suggest this is not necessary, and may not be desirable, but there is a lot of inertia. 

There is always some mental disruption when a student is asked to change paradigms, since a paradigm is built on a consistent mental model that is also relatively closed, not needing outside explanations. Paradigm shift is, in general, difficult, even for experts. The HS or undergraduate curriculum is short in time so most faculty are resistant, at least a bit, to require uproar in the middle of the two or four years. Much better, it is normally thought, to treat one paradigm as the main-line and any others as nice but inessential to the main goal. 

If you have a lot of chickens, you get a lot of eggs. OTOH, if you have a lot of eggs, you get a lot of chickens. Pigs, not so much. 

However, if you are going to teach any given paradigm, you need to do it well. You need to make students completely comfortable in that paradigm so that when presented with a new problem they aren't confused about how to begin or what should be the next step. Languages/paradigms should fit like a comfortable pair of shoes. I'm not certain that current OOP education is as good as it could be, actually, but that is due to my own background. If we suddenly adopted FP widely, you might well think the same thing about the then state of the art concerning FP. Change happens, but it is slow and is resisted. 

Students need two things at least. They need to be able to solve problems so that they can be successful in academia and/or the world of employment. But they also need to be able to think and be flexible so that they are able to move with the times as necessary. So we tend to teach one paradigm completely (for the first goal), but allow them exposure to others (for the second). Mostly it works. 



I'll also note that learning new languages is actually harder than it is often represented to be. If two languages are within one paradigm and have similar concepts then it may seem to be merely a question of new syntax applied to old ideas. Java and Python have similar ideas but quite different syntax. But learning the syntax of Python as an experienced Java programmer won't make you pythonic. But changing paradigms is much, much harder, even when the syntax is nearly the same. I'll note that C++ was derived from Dijkstra's ideas primarily (via Simula), whereas Java's core concepts come from Alan Kay. If you don't understand that then you can wind up programming badly in both languages.