What should we teach to liberal arts students who will take only one math course? Even professors in academic departments other than mathematics---never mind other educated people---do not know that such a field as mathematics exists.  Once a professor of medicine asked me whether it is necessary to write a thesis to get a Ph.D. in math, and then added, "After all, isn't it all already known?".  Literate people generally know that physics and biology are fields in which new discoveries are constantly being made.  Why should it be any more difficult to let people know that about mathematics than about physics?  After all, it's not as if most people who know that about physics have any idea what those new discoveries are.
Liberal arts students are often required to take one math course.  Often that course consists of a bunch of useless clerical skills.  How to do partial fractions decompositions and the like is what students are told "mathematical thinking" is about.  In some cases professors feel the one math course that the philosophy major takes is not worth attention because students who didn't learn that material in high school the way they were supposed to aren't any good.  
When a university has a course intended to acquaint those who take only one math course with the fact that mathematics is an intellectual field, there are still nonetheless numerous students who take only the algebra course whose content is taught only because it's prerequisite material for other subjects that the student will never take.
So what should we teach to liberal arts students who will take only one math course?
 A: Look at the contents of this course, by Satyan Devadoss at Williams College: The Shape of Nature,
a.k.a., the Geometry and Topology of Nature.  It was just released the The Teaching Company. [Disclosure: Satyan is a coauthor.]  To quote Herbert Wilf from the Notices of the AMS,

"A mind is a fire to be kindled, not a bucket to be filled."  The job of the teacher is to light that fire...

I think material such as that in this course is suitable kindling.
Addendum:
In that course, Satyan manages to touch upon: The Poincaré conjecture, Voronoi diagrams, the Jones polynomial, the Seifert algorithm, and
Dehn surgery.
A: An entirely practical point: I taught such a course one semester, with the COMAP book which is called "For All Practical Purposes." They supplied a set of videotapes, which I ignored. The course I gave was unpleasant for most concerned, certainly for me. In another semester I substituted a single day for a colleague who was using the videotapes. It was wonderful. I showed the video, they got something out of it, I explained a tiny bit. The real surprize to me was just how well the video was done. By now they must have DVD's, online stuff, etc. As that was in the 1990's, I assume that there are more recent incarnations of such course materials. 
A: This is a really difficult question to answer because mathematics by its very nature is the proverbial snake that swallows its own tail: You can't really explain any substantial part of it to "virgins" without some background in mathematics to begin with. Even high school algebra and geometry aren't really enough of a bare minimum to make substantial mathematics intelligible to most newbies. It MIGHT be good enough to motivate calculus and its role in physics -- and perhaps some group theory and linear algebra through geometry --but anything else is going to be tough. And today's students (in the US at least) aren't even guaranteed to have a good plane geometry background anymore, which was once automatic in anyone that completed high school. 
In theory, you'd like a course that a) makes these students aware of what mathematics is and why it is important and b) perhaps makes enough of an impression on beginning students to whet their appetite for more. If I was forced to teach such a course knowing in all likelihood it would be the only required course they would take, I would probably teach a history of mathematics course and try and make it as geometric and story-driven as possible. Tell them about Archimedes, the great Greek traditions, and what great advancements were already made, such as proving the world is round and computing its circumference. Debunk the myths, like Newton and the apple. Tell them about the little known and fascinating figures, like late-bloomer Weierstrass and child prodigies like Gauss, tragic figures like Galois, Abel, and Turing. And lastly, tell them about the Millenium Problems, so that they can appreciate the fact that math indeed has real-world value — a million dollars! — to some people. But above all, tell a great story they'll always remember you for. 
That's what I'd do.
A: In the May issue of the Notices of the American Mathematical Society, Underwood Dudley
posits that the purpose of a mathematics education is to teach people how to reason. This would suggest that the purpose of a liberal arts mathematics course should be, more or less, to have students perform calisthenics in reasoning. We could teach mathematical push-ups and sit-ups or we could package the calisthenics into activities that have the greatest chance of maintaining student interest.
To maintain student interest in physics, David Goodstein of Caltech created a course that intertwined history and experimental observation. Maybe liberal arts mathematics courses should follow his hueristic.  
A: Among basic numeracy issues that I have smuggled in to the classroom (I say "smuggled" because there is a list of topics that I'm supposed to cover) is Euclid's algorithm for GCDs and how to use the results to reduce fractions.  No student has complained about this even though I've given them no written material on it besides assigned problems (and sometimes students required to take a course they'd rather not take are inclined to find things to complain about).  See #2 at http://www.math.umn.edu/~hardy/1031/hw/2nd.pdf.  Another addresses the habit of almost everyone to round 400 to 399.99823764, etc.  One of the simplest examples is when you want to evaluate something like $(8/3) \times 57$.  Students use their calculators to find that $8/3 \approx 2.667$, then multiply that by $57$, getting $152.019$, although in fact 57 is divisible by 3.  Sometimes they even do that when the question is "How many....?"  (See #5 at http://www.math.umn.edu/~hardy/1031/hw/1st.pdf.)  #4 at http://www.math.umn.edu/~hardy/1031/hw/1st.pdf is also a nice "basic numeracy" problem.
Why is multiplication of finite cardinal numbers commutative, despite the seeming asymmetry in its definition?  That's really basic numeracy, but "theoretical" and at the same time very concrete.
Mentioning past geniuses also seems worthwhile.  I tell them Carl Gauss was the most famous person to live on earth in the 19th century (except people who did not work in the physical or mathematical sciences) and give them a copy of Wikipedia's "list of topics named after Carl Gauss" (the one on Euler is much longer; there are also such pages on Riemann and various others).
Basic probability seems worth presenting to a broad audience since there are so many different subjects that rely on statistics.
The combinatorial stuff that some basic probability problems rely on afford an opportunity to do "theoretical but concrete" mathematics, as in #2 or #6 at http://www.math.umn.edu/~hardy/1031/hw/1st.pdf (#6 was discussed in class before it was assigned).  ("Concrete" is necessary at this level; there is no hope that these students will learn to understand such material at a less concrete level before the semester is over.)
I more frequently use exercises to call students attention to something than to challenge their cleverness.
Oh: As long as I've mentioned "numeracy", how about #1 at http://www.math.umn.edu/~hardy/1031/hw/7th.pdf?  It actually seems as if some instructors are not aware of this problem.  Why do they neglect to know about such a thing?
Today I've mentioned elsewhere on math overflow that I was amazed at how much could be done in the book by Freedman, Pisani, Purves, and Adhikari with so little knowledge of math on the part of the students.  That things like that can be done encourages me to hope that there is some way to present the concept of isomorphism to non-mathematical freshman.  It's what math is all about.  Math is about "abstract structures" in the sense that it doesn't matter whether the chess pieces are made of wood or are images on the computer monitor, nor does $2 + 3 = 5$ depend on whether you're counting oranges or supreme court justices.  Two things are the same abstract structure iff they're isomorphic.
And isomorphism makes "bypass operations" possible; there must be some of those that can be presented to freshman.
A: I have some experience of teaching a course in Mathematics for libearal arts and social science students. It was called last year "the beauty of mathematics". 
Here is a blog post about the course, and the course page which contains all the presentation (in Hebrew). 
The main topics of the course were
Numbers: irrational numbers, imaginary numbers, different representations of numbers, prime numbers and their properties.
Shapes: Geometry from two dimensions to many dimensions.
Infinity: The concept of infinity. The paradox of motion. How to add up infinitly many numbers.
Riddles: Mathematical puzzles and riddles.
Models: Mathematical models as the gate to science.
Probability: The mathematics of luck.
Games: mathematical games and the theory of games. Mathematics in social sciences.
Of course, there is much to be chosen from and it is quite important not to squeeze too much to a single course. 
A: Teach them to make computer graphics that represent mathematical concepts.
A: We had a discussion about this at the sbparty.  The conclusion I came to is that I would cover the following three topics.


*

*Basic numeracy.  The main goal of this portion of the class is to convince people that 1 million dollars is a small amount of money, but 1 billion dollars is a large amount of money. (For example, if you won a million dollars tomorrow you should not drop out of school, but if you won a billion dollars you should do whatever you want to do.)  Related topics include Fermi problems, understanding the scales of things, etc.  If there's enough time then this unit would finish with explaining how exponential growth is much faster than linear.

*Basic statistics.  I actually don't know that much statistics so I'm not totally sure what this should cover, but the goal is for people to be able to understand polling, sampling, and common statistical fallacies.  People should leave this unit understanding what the margin of error means in a poll, some rough idea of standard deviations, and why sampling would improve the accuracy of the census.

*Why is math fun?  The goal of this section is to show people some cool things that illustrate what mathematics is as practiced by mathematicians.  The student's would not be expected to really learn anything here, but instead would hopefully be persuaded that mathematicians do some interesting things.  In particular, it would be nice if a person in the class who would enjoy advanced math classes (but doesn't know that yet) could see that math is something they would like.  If I were teaching this class I'd probably do Farey Fractions since that's my go to topic, but there are lots of good options (platonic solids, Cantor set theory, RSA, etc.).


The third section would be shorter than the first two and less heavily covered in the exams.
A: Teach them something surprising, something memorable. 
Looking through the contents of "The Heart of Mathematics: An Invitation to Effective Thinking" by Edward B. Burger and Michael Starbird, among other things they talk about number theory (up to RSA encryption), irrational numbers, different sizes of infinity, the fourth dimension, knot theory, fractals, and counterintuitive probability.
These are all the kinds of things that excite mathematicians, and we should try to give our students some sense of that kind of excitement. Burger and Starbird's book is designed for a ``liberal arts'' type course, and I think they demonstrate that it's possible to give an understanding of what's going on in a way that is at least somewhat palatable to non-mathematicians.
A: In my second year at university I was approached by some staff members of our university's English department to develop a theatrical production that TAUGHT mathematics.
The project was to be a part of a larger movement to try to increase interdisciplinary learning through the medium of the arts.
The deal was I could do this production in exchange for having to do my second year essay, which is normally a compulsory module, and I would be marked instead for the theatre piece. In the end it was for exactly these reasons that it fell through since I knew that the theatre piece would take a far more significant amount of time than the 7 page essay that I would otherwise be writing.
However before ducking out, I did put some thought towards what would be most suitable to teach. In the end I decided that set theory would be the way forward, and I propose this as a sensible answer to your question.
I think that there is a great motivation to teach students about set theory. At its most basic level this would be drawing Venn Diagrams, and asking them to write certain unions and intersections in disjoint forms; or one could follow a book like Halmos. But along side this the teacher can introduce the philosophical aspects, which should go some way toward arousing their interests. Further more, the historical aspect of the topic is fascinating. And (if it couldn't get better), the number of paradoxes present in the topic which are (often) easily explainable to the uninitiated means that there will be a clear sense of how deep mathematics is, and how alive it still is today.
A: This year I have been teaching maths course to liberal arts and linguistics students. My practice is: tell them what maths appears in our everyday life -- tell them the *.mp3 and *.jpg files in computer are actually using the idea of function approximation; tell them the various application of maths in contemporary information technology field such as the self-error-correcting-code system, the Code-Dividing-Multiple-Address cellphone technology, etc.
When the students know maths is around themselves, not just laying in the textbook, their interest will automatically come out. Even they cannot understand the logic and the principle finnally, they at least get an impression that maths is very useful in modern technologies.
A: In surveying the other responses to date it seems like many people have assumed that without assuming calculus the most we can hope for teaching undergraduate students is probability, statistics, fractions/percentages, brain teasers and puzzles.
Aren't we shooting too low?
For an extreme example of how far we might actually push such a course consider a quote of Arnol'd's in On teaching mathematics:

By the way, in the 1960s I taught group theory to Moscow schoolchildren. Avoiding all the axiomatics and staying as close as possible to physics, in half a year I got to the Abel theorem on the unsolvability of a general equation of degree five in radicals (having on the way taught the pupils complex numbers, Riemann surfaces, fundamental groups and monodromy groups of algebraic functions). This course was later published by one of the audience, V. Alekseev, as the book The Abel theorem in problems.

Set aside the hairy issue that this high school, which is already far more specialized than US high schools, was one of the premier math/physics high schools in Russia. Rather, pay attention to the fact that the first 220 pages of Alekseev's book is self-contained and no calculus is necessary.
Also, consider the idea of a year-long course following Penrose's Road to Reality. Showing people mathematics' role in unraveling the secrets of the universe has always seemed far cooler to me than other tactics for inspiration.
Let me be perfectly clear that I think actually requiring a course such as Arnol'd's across the board is overly optimistic. However, I think that by selecting the topics of such a course to reflect what mathematicians generally value could go a long way towards providing both a cultural appreciation of modern mathematics (as Lockhart's Lament would like) and an opportunity to think rigorously about initially simple objects (groups) and then more complex but visual objects (Riemann surfaces).
If people are pessimistic that "liberal arts majors" don't have the goods to think about group theory, then I would much rather have a history of mathematics course that follows something like Stillwell's Mathematics and Its History, leaving students with the impression that mathematics has a rich philosophical undercurrent, than bore them with a meaningless pursuit of graph theory, probability and a smorgasbord of seemingly unrelated topics.
The prevalent idea among many people seems to be that we have to make sure that basic numeracy is in place and that this is the math department's job. I don't think that innumeracy is a problem with the school system as it stands. People just forget their middle school and high school math because to them mathematics is an uninspired dead subject that is just plain boring. Let's change that.  
A: The aim I set for myself is to get the students to the point that they can understand how somebody else can enjoy math.
A: I think this question can actually be interpreted in two different ways, since there are essentially two possible courses to give:


*

*One whose purpose is to enrich the students' lives (as Ilya Grigoriev put it in his comment) - such a course would probably do best to adapt ideas mainly from Noah Snyder's answer - scales, statistics (probabilistic thinking), and I'd add a few other topics (maybe small logical puzzles to make students see how "thinking mathematically" may have a positive effect on their analysis of every day situations).

*A course whose main purpose is to convince students that "math is great". Make them drop the false impressions they've been fed with their entire lives, about mathematics being a "dead science" ("haven't all math problems already been solved?") - this can be achieved through looking at mathematics from a historical perspective, especially putting emphasis on problems solved recently (say last 50 years), open problems and new emerging fields in mathematics. Making them see that math can be fun is perhaps the ultimate goal, as Kevin O'Bryant mentioned.


Now the question arises: which of the two courses should we teach? Morally, if we think of the benefit of our students, we'd have to pick the first. But if we are mainly interested in "advertising" (which I don't think is a bad idea!), we should pick the second. Perhaps if such an "advertising course" is sufficiently good, it would convince them to take a second course, more along the lines of #1 above?
A compromise could be to divide the course into two parts - after we've convinced the students that math can be cool, you can go on and teach them more traditional stuff that will be beneficial to them.
A: I think there is nothing that is both as elementary, useful and fun as elementary probability. Probabilistic thinking is relevant to decision making and extremely underdeveloped. Even Paul Erdös got the Monty Hall problem wrong, when he was first confronted with it. So probability is certainly not trivial. The amount of formalism needed is very small, so students afraid of complicated expressions will not be scared off. One can cover a wide range of conceptual and practical problems, from brain teasers, probabilistic paradoxes to how one should interpret medical tests. 
I think there are some rather simple concepts not widely understood that should be really hammered into peoples heads such as (elementary) conditional probability, differences between causation and correlation, selection bias etc.  
A: A well-thought-out example, that may serve as a good model for a course on mathematics for humanities students, is Gerald Holton and Stephen G. Brush's Physics, the Human Adventure: From Copernicus to Einstein and Beyond (Rutgers University Press, 2001). It's the third edition of Introduction to Concepts and Theories in Physical Science (Addison-Wesley, 1952). 
Holton and Brush is not intended to be an "easy" book. The authors write in the preface, "The book is intended for a year course (two semesters or three quarters) in a general education or core program, taken primarily by nonscience majors  who have an adequate background in mathematics (up to but not including calculus)" (xiv). The goal of their book is to present "a comprehensible account -- a continuous story line, as it were -- of how science evolves through the interactions of theories, experiments, and actual scientists. We hope the reader will thereby get to understand the scientific worldview. And equally important, by following the steps in key arguments and in the derivation of fundamental equations, the readers will learn how scientists think" (xiv; emphasis in original). 
One of the features that makes Holton and Brush unique is that the book makes use of both the history and the philosophy of science to create the story line. A course on mathematics for humanities students ought to make use of the history and philosophy of mathematics for similar reasons. Doing so creates a context for students so that they can learn how mathematicians think.
A: Let me take a different approach: that of the liberal arts student. Since my interest vary I took sailing, theater arts, philosophy, etc and outside of school fencing related martial arts. Three segments stand out in my memory:


*

*10 years ago when our Calculus
teacher was writing the value of pi,
he just kept going to 9th decimal places and we were all
awed by the demonstration

*Our Linear Algebra professor used to quip: Parlez vous mathematique? and he even instilled the idea in me that: Mathematics is study of forms which will remain with me forever even though I could not complete the course (2x).

*The last is in our martial arts class related to stick fighting: It's not about just clicking sticks, but you must showcase yourself. 


Now there have been some remarkable math personalities reading from biography like Tarski who would bring incredible energy to the classroom. I felt lack of it during the class.
Keeping these in mind and Howard Gardner's theory of multiple intelligence where we acquire learning in our unique way, I humbly point to this question in Math.SE which I opened under former account and admittedly the accepted bounty does not do justice to other answer, which may have been edited later.
As the thread would show, I as a student whose interests are bent more on humanities side, would like to take a still-life of a daily example, if I was the teacher, and break it down mathematically. How many sands are there in the universe? Why should 2+2 = 4? (and keep carrying on the conversation with the student). Anyone interested in knitting and crochet: how would you describe the concept of knot in mathematics? etc..
But at the end, it's about showcasing your art. Sometimes if a professor memorizes, mass amount of information and gives a dramatic showdown in class without looking at notes, it will be etched forever in student's mind.
A: I think a little bit of mathematical logic should be included.  Not-too-technical descriptions of what formalized proofs are, what models are, Tarski's definition of truth, Gödel's incompleteness theorem, the halting problem for Turing machines.  Also Cantor's diagonal proof that the reals are uncountable, and maybe some historical info about how the religious community reacted to that theorem (apparently they reacted badly, see the wikipedia biography of Cantor).
Chaos and the butterfly effect deserve a mention.
A few examples from computational complexity theory could be cool.  Scott Aaronson has some nice ones here.
I once explained public-key cryptography to a music major (showing how RSA worked) and I think he understood it and appreciated it.
A: There are nice options if your university's students all took calculous in high school.  In that case, you might try some light weight mixture of elementary differential equations, recurrence relations, generating functions, and game theory.
You start out by explaining how differential equations arise in various branches of science.  You next introduce recurrence relations explaining the distinction between discrete and continuous mathematics, indicating how they arise in science and game theory.  You then remind them about Taylor series and introduce the method of generating functions, showing that differential equations are used in solving discrete problems too. 
In this way, you could provide a cohesive course that builds upon itself like mathematics is want to do, requires computational homeworks, seriously discusses the notion of infinity, touches upon numerous applied topics, and shows how mathematics can be simultaneously convergent, surprising, and useful by introducing generating functions.  
If they're very quick, there is considerable flexibility for discussing algorithm running times and P != NP, or Dirichlet series generating functions and the Riemann Zeta function, or whatever.
You'd want to verify that elementary differential equations and Taylor series are still part of the AP Calculous AB syllabus, as well as the percentage of incoming students who've had that course.  You should however suppress anything that requires multi-variable calculous that only falls under the AP Calculous BC syllabus, which presumably few student's took.
A: How to calculate a 15%, 17.5%, and 20% tip without using a specially designed application. In all seriousness, a mix of practical math and practical summaries of problems which are yet to be solved, etc. 
