As someone who has taught a few of the suggested topics (philosophy, logic, and critical thinking), I have to agree that Critical Thinking is the best option. By that I mean a course covering argumentation, not as an abstract formalism, but as a practical activity people engage in together, whose function is to resolve differences of opinion. As such, it has as much to do with communication, understanding your opponent's views and goals, and the nature of evidence, as it has to do with premises, conclusions, and fallacies.
Critical thinking is a better option than skepticism because, although the latter term is sometimes used synonymously with the former, it more properly means withholding assent until sufficient evidence is given. But this is only a small part of critical thinking, which also involves knowing when to assent, how to assess reasoning and evidence, etc.
It's better than logic, for four reasons. First, the logic in almost all arguments outside of academic and legal contexts is very simple, simple enough that formal instruction is no more helpful than instruction in proofreading. Second, most unacceptable arguments are not due to logical errors, but rather their taking as starting points propositions that are false or not acceptable to all the parties in the debate. Logic is garbage in, garbage out.
Third, introductory logic courses almost exclusively teach formal logic, specifically classical propositional and sometimes first-order logic, but these logics cannot represent most ordinary types of reasoning (including inductive reasoning) without considerable distortion. There is an ongoing project in Philosophy and Logic to represent all valid forms of reasoning in something like first order logic, but most reasoning requires formalisms so complicated they are only covered in advanced courses (e.g., first-order modal logic, counterfactual reasoning, epistemic and doxastic logics), and some of it has resisted any convincing formalization (moral reasoning, i.e., deontic logic). E.g., not until well into graduate school did I learn a system capable of adequately formalizing "Galileo believed the Earth moves. The Earth moves. Therefore, Galileo believed something true" (Church's logic of sense and denotation, which is highly complicated and a work in progress). Philosophers and Logicians typically do not work on practical abilities to deal with simple arguments, but rather developing mathematically precise formal languages and semantics for them. Introductory logic courses, as traditionally taught, make an effective introduction to this ongoing project, but a pretty poor source of basic reasoning skills.
Fourth, although students who already have exceptional reasoning skills will get a lot out a logic class, and work on their own to apply the formal insights to discourse and thinking outside that class, in my experience most students have difficulty bridging that gap on their own. While logic is commonly taught in philosophy departments, what helps philosophy students understand and assess arguments is talking about them, not formalizing them (except for the most mathematically or logically inclined). Years of experience reading and teaching philosophy has done more for my reasoning skills than the logic courses I have taken and taught, and I think that is how it generally goes for people in my field. So I see little value in teaching formal logic, or even an informal version of basic classical logic, as an introductory course for everyone. However, it would be useful to teach a bit of logic to everyone, as a (relatively small) part of a critical thinking course.
"The four building blocks of the universe are fire, water, gravel and vinyl." -- Dave Barry