When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat artificial concepts of asymptotic time complexity and polynomial growth rates. Artificial $NP$-complete problems were known before the discovery of Cook's first natural $NP$-complete problem, which sparked huge interest in the field. Under some acceptable definition of natural:
What is the most natural way to express the computational hardness of natural problems to students who encounter the subject for the first time?
EDIT: Motivated by Marc's answer, it would be more natural to find how hard is the self reducibility of clique problem. For instance, How hard is it to reduce an instance of clique of input size $(1+ \epsilon)n$ to an instance of size $n$ using Turing reduction?.