The context
In my country, when the concept of function needs to be introduced in math classes, most teachers will simply talk about $f(x)=c$, $f(x)=ax+b$ and $f(x)=1/x$ (constant, linear and inverse functions). (This is enough for the first year; the following $2$ years deal with second degree polynomials, exponential and logarithmic functions, trigonometric functions, etc.)
The basic properties of functions (domain, range, maximum, etc.) as well as the concept of reciprocal functions ($f^{-1}(x)$) are also briefly discussed.
However, it is rarely explained what functions truly are. Most students don't understand the usefulness of the "$f(x)$" notation versus "$y$" (for example, $f(x)=ax+b$ versus $y=ax+b$). When asked: "explain what a function is", most will say "it's a line", "it's a curve", "it's a graph" or "it's a formula" (these are not too far from the truth, but not quite right), or worse, will not be able to say anything about what functions are.
There is even a scary amount of students who have studied functions for more than two years and still struggle to explain the concept clearly.
Source of the problem
I believe part of the problem stems from the fact that it is never quite explained clearly what functions are. For example, it is never mentioned that functions are a rule that associates elements from one set to another. Incidentally, students never develop a real intuition of what functions do; they think "formula" and not "input" $\Rightarrow$ "output".
Note: I might be making generalizations here, but it is my perception as the same problem was there years ago when I was in school and is still present today.
Example of one way to introduce functions
One example that I've thought of but I'm sure is not optimal is to present a set:
$$\mathbb{L}=\{a,b,c,d,...,x,y,z\}$$
and another set:
$$\mathbb{E}=\{\text{vowel},\text{consonant}\}$$
and invent a function $f$ whose job, whose "function", is to assign each letter to the right category (vowel and consonant).
Then I can explain many things like why $f(x)=y$ works (because for example, $f(a)=\text{vowel}$ but $f(b)=\text{consonant}$). I can also explain that $\mathbb{L}$ represents the domain and $\mathbb{E}$ the range of the function. However, the example would be bad to explain what $f^{-1}(x)$ is and there is ambiguity if I try to say that $f(x)=y$ because really $f(x)=\text{consonant}$; so it is definitely not a perfect example.
The question
Do you know of any simple (think "short"), elegant, unforgettable and ideally "all-encompassing" ways to explain the concept of functions before actually starting to teach about real functions, formulas and graphs?
Thank you for your time and propositions.