What are the most important results (and papers) in complexity theory that every one should know? A few years ago Lance Fortnow listed his favorite theorems in complexity theory:
(1965-1974)
(1975-1984)
(1985-1994)
(1995-2004)
But he restricted himself (check the third one) and his last post is now 6 years old. An updated and more comprehensive list can be helpful.

What are the most important results (and papers) in complexity theory that every one should know? What are your favorites?

 A: I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)
Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)
The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)
As for the last 6 years... I'll have to think about my choices for the "best papers" since then. Expect an update to this answer later. I think the following work over the last six years should be among those that everyone should know about. That doesn't mean that I think they're "best", it just means I am trying to answer the original question. It's a very biased list.

*

*Irit Dinur's combinatorial proof of the PCP theorem


*Omer Reingold's logspace algorithm for st-connectivity


*Ketan Mulmuley's geometric complexity theory program


*Subhash Khot's Unique Games Conjecture and what it entails (this was initiated earlier than 6 years ago but it has become much more important in the last 6 years)


*Russell Impagliazzo and Valentine Kabanets' "Derandomizing polynomial identity testing means proving circuit lower bounds"


*Lance Fortnow et al.'s time-space lower bounds for SAT (this is excluding all work that I have personally done on this, you can decide for yourself if you should know about that)
I left out a bunch of very important things because the list is 6 items. Sorry.
A: My favourite results are (1) the existence of NP-complete problems (Cook), (2) the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle,
and (3) Fagin's characterization of NP in terms of second order logic.
I am not so much interested in the large number of proofs that show that a certain problem is NP-complete, but the fact that there is some problem that is NP-complete is remarkable
and important.  And Cook's SAT is actually natural.  (2) shows that several approaches will not work when one wants to settle P versus NP.  (3) gives a much more natural definition 
of the class NP.  Fagin's formulation (NP is the class of graph properties (of finite graphs) that can be expressed with a formula that has an n-ary second order existential quantifier in front, followed by a first order formula) indicates that NP vs co-NP is a very fundamental question as well (can second order existential quantification be replaced by second order universal quantification?). 
A: I think you should add as a recent result the proof for QIP=IP=PSPACE
A: There's the Bazzi/Razborov/Braverman sequence on fooling AC0 circuits.  
A: Well I guess after Cook, Karp's paper "Reducibility among combinatorial problems" is the second most obligatory and canonical thing to mention. This paper was the first to demonstrate to the world the diversity and ubiquity of NP-complete problems.
