In this case it's more mathematical. We have the constitution, which is axiomatically constitutional. The constitution says that the Supreme Court decides constitutionality. The Supreme Court says that the civil rights act is constitutional. Ergo the civil rights act is constitutional.
If you assert that the civil rights act is not constitutional, then you are implying that the constitution itself is flawed.
But then again, nothing stops you from holding the opinion that logical constructs are false.
But you missed the point about what the lawyers & constitutional scholars do, which is to twist words so that they wind up having a far different meaning than the plain language and study of history would suggest. For example, consider the 2nd Amendment: only now are we slowly starting to move away from close on a century of laws based on twisting its clear intent (and common practice) to something almost exactly the opposite of the original intent.
Now if you say this was Constitutional because the Supreme Court decided to accept the twisted meaning, you're of course correct. Just as it's also correct that it's slowly becoming unConstitutional because a majority of justices no longer accept that reasoning, at least in some cases. But that's rather ignoring a larger point, rather like the state legislatures that mandate teaching "creation science". Legislation doesn't determine truth.
It's one thing to say "the founding fathers would not have liked this." It's another thing to say it's unconstitutional. Some of the founding fathers were real dicks, so I'm not necessarily all that keen to abide by their wishes.
edit: but I do see what you're saying, I just think (some) libertarians are going to need better arguments for (some) of their craziness
There is nothing in the constitution that explicitly spells out the power of judicial review for the Supreme Court. It only exists through implication and interpretation. If a person does not believe the power of judicial review exists for the Supreme Court by their interpretation of the constitution, then the Supreme Court has no authority whatsoever on what is constitutional. The constitution is not explicit on this matter, so to say the constitution says the Supreme Court gets to decide is not correct, or is at least open to interpretation.
I am fine with judicial review and the Supreme Court, as it is preferable to an unchecked government.
In terms of public accommodation laws, the real problem before the 1964 Civil Rights legislation was governments that forced segregation or discrimination by private businesses through laws. There is a place for federal law which prohibits these kinds of laws from being enforced.
I personally come down on the side of freedom of association trumping public accommodation. One benefit of allowing businesses to discriminate is that I get more information about the owner of a business. If a business is one that chooses to discriminate, then I know quite a bit about the owner and can choose to not support that business. Now with public accommodation laws, that information is removed from public view.
I have no problem with laws or regulation that prevent actual harm to another individual according to the non-aggression principle. For me, though, the bar is going to be set pretty high in terms of proving an actual harm and proving that harm is not avoidable. By avoidable, I mean not doing something (like going to a restaurant). I don't mean being forced to do something (like leave your house to avoid a harm.)
What I don't understand about non-smoking laws is that you are not allowed to smoke in a business, which is private property, but you can in many public places such as walking down a sidewalk.