In equal protection challenges, the Supreme Court's "strict scrutiny" standard applies only applies to certain types of laws or other government actions. It applies either where the government action affects a right the Court considers fundamental, or where it makes a "suspect classifications." A law only does this if it classifies people by race or national origin--and maybe by alienage.
States can and in some cases do prohibit discrimination in public accommodations on more grounds than are recognized in the federal public accommodations law. The constitutional basis for that law, which is part of the Civil Rights Act of 1964, is Congress' power to regulate interstate commerce. The reason they had to reach for that good ole catchall, the Commerce Clause, is that it is usually private persons who own and operate public accommodations, and almost nothing in the Constitution prohibits discrimination by private persons. Anyone can read Katzenbach v. McClung (the "Ollie's Barbecue Case") and decide for himself how persuasive the Court's reasoning about the effect of race discrimination on interstate commerce is.
States can go further in these laws because their authority to make laws and policies is inherent, rather than granted by the Constitution of the U.S. But they have sometimes gone too far and run up against the First Amendment. In both cases where the Supreme Court held a state public accommodations law unconstitutional, the law prohibited discrimination on the basis of sexual preference, and private persons had discriminated against homosexuals. Massachusetts' law, which defined the Boston St. Patrick's Day Parade as a public accommodation, was held unconstitutional as applied in Hurley for violating the parade organizers' freedom of speech. New Jersey's law, which defined the Monmouth council of the Boy Scouts of America as a public accommodation, was held unconstitutional as applied in Dale for violating the council members' freedom of association.
What Marbury v. Madison stands for is more complicated than most people think, but I'll mostly leave that for another post. Chief Justice Marshall's brilliant, clever arguments in that case have been discussed a lot over the years. In effect he arrogated the power of judicial review to the Court, and yet not a power of review as broad as what it's usually taken to be now. I don't accept that the Supreme Court has the sole word or the last word on what this or that part of the Constitution means.