How do you define functions for non-mathematicians?
Solution 1:
For fun, I like to liven-up the "black box"/machine view of a function by putting a monkey into the box. (I got pretty good at chalkboard-sketching a monkey that looked a little bit like Curious George, but with a tail.)
Give the Function Monkey an input and he'll cheerfully give you an output. The Function Monkey is smart enough to read and follow rules, and make computations, but he's not qualified to make decisions: his rules must provide for exactly one output for a given input. (Never let a Monkey choose!)
You can continue the metaphor by discussing the monkey's "domain" as the inputs he understands (what he can control); giving him an input outside his domain just confuses and frightens him ... or, depending upon the nature of the audience, kills him. (What? You gave the Reciprocal Monkey a Zero? You killed the Function Monkey!) Of course, it's probably more appropriate to say that the Function Monkey simply ignores such inputs, but students seem to like the drama. (As warnings go, "Don't kill the Function Monkey!" gets more attention than "Don't bore the Function Monkey!")
The Function Monkey comes in handy later when you start graphing functions: imagine that the x-axis is covered with coconuts (one coconut per "x" value). The Function Monkey strolls along the axis, picks up a "x" coconut, computes the associated "y" value (because that's what he does), and then throws the coconut up (or down) the appropriate height above (or below) the axis, where it magically sticks (or hovers or whatever). So, if you ever want to plot a function, just "Be a Function Monkey and throw some coconuts around". (Warning: Students may insist that that's not a coconut the Monkey is throwing.)
Further on, you can make the case that we're smarter than monkeys (at least, we should strive to be): We don't always have to mindlessly plot points to know what the graph of an equation looks like; we can sometimes anticipate the outcome by studying the equation. This motivates manipulating an equation to tease out clues about the shape of its graph, explaining, for instance, our interest in the slope-intercept form of a line equation (and the almost-never-taught intercept-intercept form, which I personally like a lot), the special forms of conic section equations (which aren't all functions, of course), and all that stuff related to translations and scaling.
Parametric equations can be presented as a way to let the Function Monkey plot elaborate curves ... both in the plane and in space (and beyond).
All in all, I find that the Function Monkey can make the course material more engaging without dumbing it down; he provides a fun way to interpret the definitions and behaviors of functions, not a way to avoid them. Now, is the Function Monkey too cutesy for a College Algebra class? My high school students loved him, even at the Calculus level. One former student told me that he would often invoke the Function Monkey when tutoring his college peers. If it's clear to the students that the instructor isn't trying to patronize them, the Function Monkey may prove quite helpful.
Solution 2:
The way you've restated the definition is fairly common in contemporary high school books in the U.S. (perhaps changing "links between two sets" to "ordered pairs"). What I've seen a lot of in middle school and earlier algebra settings is the idea of a "function machine." The function machine graphic below is from FCIT (©2009), but a google image search for function machine will show you many different ways the concept can be visualized.
While this probably pushes the idea that a function has a formula, I'd claim that "rule" could be as general as a specific listing of which inputs map to which outputs, as in your definition. To me, the prevalence of this machine metaphor in middle school contexts suggests that it works well for students who do not necessarily yet have a sense of symbolic algebra. I've seen function machines used as low as 3rd grade.
Solution 3:
I just wanted to add a few cents to this post to say that Isaac's statement "I've seen function machines used as low as 3rd grade" is quite true. I teach kindergarten and 1st grade, and I use function machines with my students, mostly when introducing the idea of complements in relation to addition and subtraction. It's a standard part of the "patterns and algebra" portion of the Everyday Mathematics curriculum. Functions are honestly NOT a challenging concept for my students to grasp when presented in this manner, hence, I am absolutely confident that your College Algebra students will be just fine! :)