When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.
But when we get to knapsack and solve it via DP, they are confused. For example, the conventional approach to knapsack for $N$ items and a $W$-capacity bag is the straightforward $O(NW)$ DP method. But I then point out that $W=2^n$ and therefore DP is exponential time. This invariably causes objections, confusion, and lots of doubt. I have yet to find a way of explaining this that makes it clear. Can anyone help?
Oh, and they haven't seen Turing machines, so that's off-limits.