Some theorems give far more than you feel they ought to: a weak hypothesis is enough to prove a strong result. Of course, there's almost always a lot of machinery hidden below the waterline. Such theorems can be excellent starting-points for someone to get to grips with a new(ish) subject: when the surprising result is no longer surprising then you can feel that you've gotten it.
Let's have some examples.
Every compact metric space is (unless it's empty) a topological quotient of the Cantor set.
What, every compact metric space? Yes, every compact metric space.
For me, the theorem that every subgroup of a free group is free is a good example of this: it seems to come for free from covering spaces and the fundamental group, but really all the heavy machinery is just moved underground.
Wedderburn's theorem: "Every finite division ring is a field." This is really astonishing if you think of quaternions: nothing analogous in the finite case.
Then of course the classification of finite fields is also very beautiful: exactly one with p^n elements (p a prime and n an integer) and no others.
And as a bonus, Wedderburn's theorem is one of the crispest in all of mathematics: seven words ( or six and a half if you replace division ring by skew-field).
Isn't almost every theorem in mathematics an example of a theorem "for free"? One defines natural numbers, and then it follows each of them is a sum of four squares; one defines a notion of a continuous function and of Euclidean space, and Brouwer's fixed point theorem follows. Surely, that is amazing!
With that said here are a handful of the example that lie closer to the surface:
Complex-differentiable functions are infinitely-differentiable, and in fact analytic.
A function of several complex variables that is holomorphic in each variable is holomorphic in all of them (if it reminds you of 'theorem' that a function that is continuous in each variable separately is continuous ... well, then, it should). That is Hartogs' theorem.
Any bound on the error term in primes number theorem of the form $\psi(x)=x+O_{\varepsilon}(x^{a+\varepsilon})$ implies the bound $\psi(x)=x+O(x^a \log x)$.
Morally related to (3) is the tensor power trick, of which the earliest widely-known example is perhaps the proof of Cotlar-Stein lemma. One of my favorite examples is lemma 2.1 from a paper of Katz and Tao on Kakeya's conjecture.
I had that feeling of getting more than you ought to a couple of weeks ago when reading the first chapter of Rota and Klain's Introduction to Geometric Probability. In particular, I was familiar with the usual derivation of the probability of Buffon's needle crossing a line. So it was amazing to read the solution to a harder problem, Buffon's noodle, which is solved by appealing to a much simpler seeming general symmetry argument. And like you describe, it forms a kind of teaser trailer to draw you you into the rest of the subject.
Faithfully-flat descent:
It tells you that you can construct quasicoherent sheaves locally on a faithfully-flat cover. This is pretty amazing, because quasicoherent sheaves are, a priori, only Zariski local. So to specify a sheaf it requires a lot less data than it initially appears.
My "canonical example" is Banach-Steinhaus in functional analysis: that, in nice locally convex topological spaces (Banach will do), weakly bounded (or pointwise bounded) implies bounded.
The machinery is quite technical, usually involving the Baire category theorem, but the result is very simple and very surprising. One especial point I like about this is that when you compare normed vector spaces with Banach spaces, then the process of adding more stuff (i.e. completion) actually limits the things that can go wrong. My intuition is that if you want to limit the bad behaviour then you need to work in smaller spaces rather than larger.
Kuratowski's theorem is a great example of a theorem of the form "the only obstructions are the obvious ones," which are always fun to learn about.
I can´t resist to mention the Cayley-Hamilton theorem. Something intuitively correct turns out to be mathematically correct too, but for non-intuitive reasons! I still remember, its proof (I´m here referring to the one using the correspondence between operation and representation) worked from my perspective like a magic, clear, simple, non-trivial and beautiful, and it also made me interested in algebra, beyond the lecture in linear algebra for first-year students. It was nice time...
Tychonoff's theorem — product of any collection of compact spaces is still compact — is amazing and incredibly useful.
The Kline sphere characterization, proven by Bing:
A compact connected metric space (with at least two points) is the 2-sphere if and only if every circle separates and no pair of points does.
Once the machinery of (co)homology is developed, Brouwer's Fixed Point seems to come for free, it's extremely straightforward to prove and has quite a lot of important consequences.
Although not exactly what you're after, the question reminds me of Reynolds' parametricity theorem, or as Philip Wadler puts it: Theorems for Free!
The basic idea is that a polymorphic construction (in a polymorphic lambda calculus) must behave uniformly, and so must preserve relations. For example, any term of type $\Pi X. X\to X$ must be the identity function, and every term of type $\Pi X Y. X\times Y\to X$ must be the first projection.
The only group with order $p$ a prime is $\mathbb{Z}/p\mathbb{Z}$
Unfortunately, a lot of these kinds of statements in combinatorics are only conjectural. One example (again, only conjectural) that came up in conversation the other day doesn't give a particularly natural result, but it's hugely surprising: the Erdos-Gyarfas conjecture in graph theory, which has pretty much the weakest possible condition for any statement of its form.
Now that I think about it, though, Ramsey theory is all about "theorems for nothing." I'm a big fan of the sunflower lemma when it comes to Ramsey-theoretical statements that deserve to be better known -- the only condition there is that your sets have to be relatively small, and there have to be a lot of them. (And that second part is conjecturally not even necessary...)
The Gauss-Bonnet theorem is a deep result relating the geometry of a surface to its topology, and its proof is very simple (the local version comes almost from nothing, and the main difficulties for the global one are topological results about triangulations). Also, it has some amazing corollaries: the integral of the gaussian curvature over a compact orientable surface is a topological invariant (${\int\int}_{S}{K}d\sigma = 2\pi\chi(S)$, where $\chi(S)$ is the Euler-Poincaré characteristic of $S$); every compact regular surface with positive gaussian curvature is homeomorphic to the sphere $S^2$; and so on.
To me, the canonical example is the Poincare Conjecture. Why SHOULD a three dimensional manifold with trivial fundamental group actually be the sphere? In higher dimensions, there are LOTS of simply connected things, but in two and three, simply connected and compact manifold determines the manifold uniquely.
I am not sure I fully understand the question. Is it the case that the theorem itself gives you a huge mileage while its proof is extremely difficult, (Characterization of finite simple group is an ultimate example; the Atiyah-Singer index theorem and the BBD(G)-decomposition theorem are other examples; or is it a case that understanding the proof (which is feasible) gives you a lot of mileage and a feeling that you got grip with the subject.
Anyway, a theorem which, to some extent, has both these features is Adams's theorem asserting that d-dimensional vectors form an algebra (even non-associative) in which division (except by 0) is always possible only for , 2, 4, and 8. (In these cases there are examles: the Complex, Quaternions and Cayley algebras.)
Artin-Schreier Theorem: If k is a field of characteristic p and strictly contained in its algebraic closure K and such that [K:k] is finite THEN (was surprising for me..) p is actually 0 and K = k(sqrt(-1)) and k is a real closed field!
A not so well known but deserving result from the "failed" thesis of Abhyankar: If K and L are algebraically closed fields contained in another algebraically closed field, then the compositum KL is not necessarily algebraically closed.
That there are infinitely many primes has some simple proofs, but I remember being shown that the sum of the reciprocals of the primes diverges which had some more machinery in it that was kind of neat to my mind.
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that $\nu(G-x)=\nu(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: $\nu(G)$ is the size of a maximum matching of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free. In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r(\{x,y\})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.
The Riesz-Thorin interpolation theorem; the complex analysis behind it never fails to surprise me.
Oh! From uniqueness of the countable dense linear order without endpoints: take (for instance) a countable ordinal $\lambda$, and consider the anti-lex order on $\mathbb{Q}\times\lambda$. This is a countable dense linear without endpoints, so it's order-isomorphic to $\mathbb{Q}$; in particular, $\mathbb{Q}$ contains a subset with order-type $\lambda$ — e.g. the isomorphs of anything $(\frac{5}{8},j)$. The same result for subsets of $\mathbb{R}$ is a more usual application of transfinite induction/AC/Zorn's lemma; here it's all hidden in the $\aleph_0$-categoricity result about dlow/oep.
I like the theorem, I think it's Gallagher's, that says: Most polynomials with integer coefficients are irreducible and have the full symmetric group as Galois group (over the rational numbers).
The precise formulation asserts that the number of bad polynomials, i.e., the number of polynomials $X^r + a_1 X^{r-1} + \cdots + a_r$ with $|a_i|\leq N$ that DO NOT have the full symmetric group as Galois group is $$O(r^3(2N+1)^{r-\frac{1}{2}}\log N)$$ (out of $(2N+1)^r$ polynomials).
Another good example is the Johnson-Lindenstrauss Lemma that says that any $n$ points in a Hilbert space can be embedded in a $O(\log n)$-dimensional Euclidean space with distances preserved upto any factor. It turns out that JL-style results crop up in many different versions, the main result itself has proofs ranging from 1 page to 10 pages, and it just keeps on giving :)