I have more NP-hard problems than you care to know about - I could probably
teach a class just going through these problems and the basic approaches.

We might differ in motiviation since my goal is usually to find an actual
heuristic solution, whereas you might be trying to motivate approximation
algorithms or the importance of NP completeness, but nonetheless here they
are.  The one thing that I think is really important about learning
NP-completeness and other theory is that you learn types of problems.  Since
some problems are actually quite-solvable in practice you learn which
heuristics can carry over between problems and so on.  By the way, since I
care about the difference between O(n) and O(n^2) not all NP-complete
problems are equal.  

Most of these are from computer-aided design for VLSI on the physical design
end.  

1.	Graph Partition and its Variants:  Given a graph, G=(V,E), (E =
O(|V|) typically), and a balance condition p (0 < p < 50), partition the
nodes of G into two sets X and Y such that the number of edges of G between
nodes in X and nodes in Y is minimized.
-	the size of min(|X|, |Y|) should be >= p % of |V|.
-	modification:  rather than minimizing the number of edges in the
"cut" minimize the number of nodes which are adjacent to an edge in the cut
(hypergraph partitioning).
-	modification:  given a hard constraint on the number of pins (the
previous metric), solve the edge minimization problem.
-	modification:  given a hard constraint on the number of edges,
minimize the pin problem.
-	modification:  expand any of these to a k-way partition

		This is a real-world problem that I deal with every single
day.  All versions NP-hard.  
		Typical solutions are
-	iterative improvement:  random partition followed by any number of
methods to "swap" nodes from side to side to decrease the overall cost.
-	simulated annealing:  similar, but randomized - you have a time
schedule, examine random swaps, and early in the schedule you allow negative
moves to escape a local minima.
-	constructive - doesn't really work
-	solve the eigenvalue-eigenvector problem on a variant of the
adjacency matrix - works well in theory, but nobody wants to be stuck
maintaining complicated numerical analysis code so nobody does it in
practice.  Also tends to be unstable.

2.	Placement:
-	Given same graph G, and an NxN grid-graph X with nearest neighbour
connections (where typically |V| is about 80-100% of N^2), find a 1:1
mapping of V into the nodes of X such that the edges of G become paths in X.
You can use multiple edges in "column 3 of X"   Your optimizations are:
-	minimuze the total "wirelength" - sum of edges of X used in the
embedding
-	given a constraint on the number of wires in a given channel,
minimize wirelength.
-	given your original graph, predict the wirelength you will need
without actually doing the placement.
-	Typical approaches: simulated annealing, recursive partition,
force-directed (like some people do graph drawing)...

3.	And really making the placement problem hard:  Now your graph is
directed, and nodes consist of both regular nodes and flip-flops.  Your goal
is to, subject to constraints such as (2), do your embedding such that the
length in X of the longest flip-flop to flip-flop path is minimized.  G is
an arbitrary graph (but with linear edges) so there are exponentially many
such paths and you can't enumerate them.
	- a sub-problem of this:  Given a placement and full knowledge,
efficiently update the "state of the graph" (distances and so on) as fast as
possible in an amortized sense, for a movement or swap of a couple nodes
(this is solving a linear-time problem in << n steps)

I wouldn't limit these problems to NP-hard either.  There are lots of n^2 or
n^3 solvable problems that cannot be executed on a graph in reasonable time.
I deal with 100,000 node graphs, so transitive closure is not really
possible.  I am interested in heuristic algorithms that can compute graph
reachablity (i.e. transitive closure) in a reasonable amount of time.

Outside of the physical design (embedding) domain, there are lots of
problems in synthesis, which is representing the graph of a set of boolean
equations (i.e. nodes are and/or gates and so on) and doing manipulation on
the graph.  For example:

4. Given a graph of 2-input nodes (gates).  Cover the graph by the minimum
number of 4-input arbitrary nodes (i.e. a new node can have 4 or fewer input
signals, and one output signal).  This is called the technology mapping
problem, and it is a preprocessor to place and route for our devices.

You asked me about benefits from solving these problems:  A 10% increase in
chip speed or number of wires is roughly equivalent to a "speed grade"
change, which is a cost factor of about 1.5 times.  That means we can
manufacture a chip for 2/3 the cost and sell it for the same price.  So even
small constants in heuristic results are dramatically important.

Hopefully that is what you were looking for.

If you want some other real-world motivation you can tell them that I am
desperate to hire people who really understand algorithms, both CAD-specific
heuristic and just simple basic network flows, binary trees and
data-structures, as well as graph theory and computational geometry-like
algorithms.