I was fortunate enough to go to a high school that had a course called Further Math (if any of you have heard of the IB curriculum, this class covered most of the topics on the IB Further Math exam) where we did basic propositional logic, Peano arithmetic, basic group theory (up to normal subgroups) and set theory up to Cantor-Schroeder-Bernstein, plus some statistics. I loved this class, although the only new thing I saw all year was CSB, and I think students might like this more than something such as calculus that they only really work with in physics class.
I would say that every high school should start students with a general logic class - introduce the mathematical formalisms (up to truth tables) and then work with real-world examples of disingenuous statements or the like. I think that students very much like learning about how adults lie to them. :P
Beyond that, as much as I hate to say it, no student should leave high school in an ideal world without knowing probability and statistics (up to the basic properties of the normal distribution). It has become such a powerful tool in our times, and yet it is so easy to lie to people with statistics: take Twain's quote, "There are three kinds of lies: lies, damned lies, and statistics."
I guess the idea here is that most high school students will be distracted enough by learning about how adults are lying to them not to notice that they're also being taught how to think critically and how to pursue truth - and that's what mathematics is really about, right?
Edit: just saw Andy's comment.
