For the record: I am a full professor at a large public university in the US. Also, I am not a lawyer (I am a mathematician).
Here are some thoughts about your situation, which I find difficult. Let me start with a story told to me by a colleague (the story is from about 30 years ago but still relevant). The Chair of the math department where my colleague was working at the time asked the Dean if the department can have a faculty hire in that academic year. The Dean replied "Yes, if you are going to hire a black female statistician." [In a way, this is similar to the situation you are in.] After a brief deliberation, the department (which is highly ranked, let's just say that it was and still is among top-20 math departments in the US) has decided not to have a faculty job search that year. (My colleague has left that department next year.) I believe this was the right decision. (Eventually, the department started to hire faculty again and the administration has backtracked on its draconian micromanaging of the hiring process.)
If I were a Chair of a department or a member of a hiring committee, I would rather have a failed search (or searches) than to accept administration's position "not to hire left-handed people." I would also conduct a fair job search and if the administration refuses to make offers to the candidates chosen by my department, so be it.
I would also have a conversation on the hiring matter with the provost in presence of more than one faculty member. Regardless of the law in your state, I would not feel good about recording the conversation unless the provost agrees on this (and I very much doubt your provost would agree). However, I would have an email exchange with the present faculty members after the conversation with the provost, confirming what was said in great detail. If it comes to legal proceedings (I hope, for your sake, it does not), such a record will be admissible in a court of law (as far as I know). At the same time, I would strongly advise against any of the options suggested by Remzi in the bottom 4 bullet points in his answer; however, I agree with his suggestions in the bullet points 1-3. I have some experience of dealing with university bureaucracy and legal system (I will not elaborate here) and even if you win, you will end up loosing several years of your life to this battle. And chances of winning are slim, the deck is stacked against you. I know, it is sad and disheartening, but this is what I know from experience and discussions with a professional lawyer (not affiliated with my university). One more thing: In general, the US legal system is very reluctant to deal with cases involving academic hiring and retention.