I would use the example of Red-Black trees, show how a two-line type definition defines the shape of all trees without having to write any constructors or access methods, and go on to show how useful pattern-matching can be when writing sophisticated symbolic manipulation functions such as the re-balancing one.
I would try to emphasize that it's a good language to write these kinds of computations in, making them concise and clear, but that the advantages may be less obvious for other categories of programs. Getting to the point where functional programmers can be considered as rational people who deliberately chose the best tool for the job they had to do would be an improvement with respect to the current situation, where they are mostly considered as lunatics by the rest of the programming community.
If that's not already clear, I wouldn't push too hard for the adoption of F# (or any other functional language). We've tried that, it doesn't work, it's time to move on. Let interested programmers come, but do not preach.
EDIT: Example taken from this nice page with a lot more detail:
type color = R | B
type 'a tree = E | T of color * 'a * 'a tree * 'a tree
let balance = function
| B, T(R, T(R, a, x, b), y, c), z, d
| B, T(R, a, x, T(R, b, y, c)), z, d
| B, a, x, T(R, T(R, b, y, c), z, d)
| B, a, x, T(R, b, y, T(R, c, z, d))
-> T(R, T(B, a, x, b), y, T(B, c, z, d))
| c, l, x, r
-> T(c, l, x, r)
In function balance, the lines that start with | are patterns. Inside a pattern, uppercase letters (or generally names that start with an uppercase letter) are constructors. For instance B is one of the constructors of type color. Lowercase letter are variables. Variables always match and can be used on the right-hand-side of -> to represent the value that was matched on the left-hand-side.
When the shape of the function's four arguments is of one of the first four patterns, T(R, T(B, a, x, b), y, T(B, c, z, d)) is returned. Otherwise, the fifth pattern is tried, and since it contains only variables, it always matches. In this case T(c, l, x, r) is returned.