Edit (Feb 2021): The content of this MathOverflow answer now forms the backbone of Chapter 2 ("Multiple Proofs") in JDH's book, Proof and the Art of Mathematics. Get a copy!
Edit (Dec 2016): Encouraged by a few comments on MO, and a few direct emails about this post, I wrote up the ideas below for a journal of math education. The citation is:
Dickman, B. (2017). Enriching Divisibility: Multiple Proofs and Generalizations. Mathematics Teacher, 110(6), 416-423. Link (no pay-wall).
Having come across this question by searching within the mathematics-education tag, I will try to answer it from the perspective of someone in the field of Mathematics Education.
Theorem: $n^2 - n$ is even for all natural numbers $n$.
It is quite possible that very good undergraduates (I am imagining freshmen) will laugh at seeing such a "theorem" written on the board; it is almost certain that professional mathematicians will scoff. Nevertheless, this is a talk that I have given in the past to graduate students in Math Education who wish to teach secondary school mathematics in the future. Under some reasonable interpretation of the parameters given in this question, I should think these two groups alike enough to outline the talk here.
After writing the theorem on the board, I then write down a collection of headers, each of which is intended as suggesting a method of proof. Once the headers are written out, I give the students three minutes to prove the theorem using one method that they are sure they can carry out, and to attempt a proof using another method they are less sure of. Below I will write the headers, followed parenthetically by the sort of remark I might say aloud as I write them down, and then a brief indication of the proof.
Cases: (Probably you don't need more than two) The cases I am thinking of are even and odd; check what happens when $n = 2k$ and then check what happens when $n = 2k+1$.
High School Algebra: (Factoring) Write $n^2 - n = (n-1)n$ as the product of consecutive integers, hence once of them must be even; so the product is even.
Number Theory: (This might not mean so much to you all as freshmen; we'll return to it later!)
Arithmetic: (I'm thinking of adding up a certain arithmetic sequence) Consider the sum of the first $n-1$ natural numbers; this gives some natural number $k = (n-1)n/2$. Multiplying both sides by $2$, we find that $n^2 - n = (n-1)n = 2k$ is even.
Geometry: (How would you represent $n^2$ with a geometrical picture?) Consider an $n \times n$ array of squares; remove the $n$ squares along the diagonal. The number of squares remaining is $n^2 - n$ and one sees symmetrically that they have been split into two groups of equal size. Hence the total is even.
Combinatorics: (I'm thinking of forming two person committees...) The number of two person committees in a group of $n$ people is some integer $k = (n-1)n/2$. Cf. Arithmetic.
Mathematical Induction: (For students familiar with induction, you might give this a shot) The base case is clear; suppose $k^2 - k$ is even and note $(k+1)^2 - (k+1) = k^2 + k = (k^2 - k) + 2k$ is the sum of two even numbers, and hence even.
The point of the above is to demonstrate that even a seemingly simple statement can be proved in a number of different ways. Such a demonstration, more than any particular theorem, is likely to be useful for all students (as specified by the OP). I usually have students discuss their answers and then use the theorem we've proved to talk about something else that ought to be useful for everyone: generalization.
The proofs above made frequent use of the following fact: $(n-1)n = n^2 - n$.
How would you generalize the following statements?
Statement A: If $n \in \mathbb{N}$, then $2$ divides $(n-1)n$.
Statement B: If $n \in \mathbb{N}$, then $2$ divides $n^2 - n$.
The former statement suggests (in my mind) that $k$ divides $k$ consecutive numbers; the latter statement suggests (in my mind) that $k$ divides $n^k - n$.
Consider when $k = 3$.
Then the statements become:
Statement A: If $n \in \mathbb{N}$, then $3$ divides $(n-1)n(n+1)$.
Statement B: If $n \in \mathbb{N}$, then $3$ divides $n^3 - n$.
Not only are these statements true, they coincide: $(n-1)n(n+1) = n^3 - n$.
This overlap breaks down for $n>3$, though, and we find that only A is true for $n=4$. (Perhaps a good point at which to mention how a single counterexample can disprove a for all statement.)
From here, the talk suggests that A is a good segue into modular arithmetic, while B practically begs us to find the $k$ for which it holds. Of course, we can answer this question using Number Theory (as mentioned early on!) and, more precisely, by appealing to Fermat's Little Theorem.
I believe the talk outlined above, with its messages about the possibility of finding multiple proofs and the interesting directions in which a simple proposition can be generalized, is a practical and doable thirty minute talk for first-year students in mathematics. I have done nothing close to applying Groebner bases or making use of ultraproducts, but I have tried to heed the OP's request to be realistic.
