Every professor teaches a theory course differently so there is no fixed answer to what has changed. But here are some trends that I have seen (from a distinctly American point of view):
- Less emphasis on automata theory, particularly for context-free languages. Many schools do away with automata theory all together.
- Less depth in computability theory. Most courses will cover undecidability but you'll less often see the recursion theory or even Rice's theorem taught.
- Does anybody still teach the Gap, Union and Speed-Up Theorems and Blum complexity measures anymore?
- Only one new theorem since the mid-70's has become a fundamental part of an undergraduate complexity course: The 1988 Immerman-Szelepcsényi Theorem stating that nondeterministic space is closed under complement.
- There has been a trend in adding some recent research in complexity as the end of a course based on the interests of the instructor: Randomized computation (though recent algorithms for primality might change how it gets taught), cryptography, interactive proofs, PCPs and approximation, quantum computing for example. Parallel computation has come and gone.