My favourite results are the existence of NP-complete problems (Cook), the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle,
and Faggin's characterization of NP in terms of second order logic.