The traveling salesman problem is apparently accessible... at least where I am, this seems to be the most popular CS problem among non-CS folks by far. I also found the following illustration of Vertex Cover quite appealing, as introduced by my algorithms instructor:
You have a road network and wish to ensure that if a car is stuck out of fuel, there is a gas station on at least one end of the road.
As a city planner, you want to minimize costs by building the fewest number of gas stations possible. This is essentially the vertex cover problem, and I have found some success in pointing out that although you don't expect to find the optimal vertex cover in polynomial time, you can find something that is only a factor of two away in polynomial time, by simply picking up both endpoints of a maximum matching (well, that last detail might be omitted depending on how keen your audience is - especially since the MM algorithm isn't exactly a two-liner).
As for an example of a 'jump in complexity' with a small change in the nature of the problem, I think the difference between checking 2-colorability and 3-colorability makes a good example. With all the publicity surrounding the four-color theorem, one might also point out that checking whether a map can be properly colored with only three colors instead of four is hard, even though we know that it can always be colored with four colors. A fair number of people find this quite startling.
Another fairly natural situation is the deadlock recovery problem in operating systems. This is modeled by the NP-complete problem of feedback vertex set - the smallest number of vertices whose removal makes the graph acyclic - and I find this to be a remarkable example as well (and is explained further in that wikipedia article).