The Federal government can't just pass a law on anything it wants. The law has to be about some power explicitly granted to the Federal government in the constitution - an enumerated power.
https://legaldictionary.net/enumerated-powers/
Otherwise the combination of being able to legislate in any area + supremacy clause means the states have no power that the federal government can't override. That's not federalism! Federalism means some powers can be centralized and others cannot, and it's the constitution that lists, or enumerates, the federal powers.
For example, the Federal government can't pass a wealth tax or a property tax. It could only pass an income tax because of a constitutional amendment authorizing the taxing of incomes. Before that amendment, it could not even pass an income tax. States, however, can. That's why there is no federal property tax or asset tax but there are state versions of both!
Now the name of the game is usually to try to link federal laws regarding regulation to the interstate commerce clause.
But the courts don't have unlimited tolerance for that, and recently they've been pairing this tolerance back. In the past, for example, Federal gun control laws banning guns in schools were allowed because of tortured arguments that guns affect schools, and schools affect interstate commerce. I mean, real stretches were common like this. But those types of arguments don't fly anymore as the courts have regained a bit of sanity when it comes to federalism.
Now when you stretch "public health" to include "mandatory vaccine", then you are really stretching interstate commerce quite a bit. This is going to raise constitutional questions as to whether you can force the entire population (as opposed to, say, airline pilots) to get a vaccine because of the interstate commerce clause. And if this is not an enumerated power, then it passes to the states and the EO is unconstitutional.