Example problems with polynomial and exponential solutions, and tiny footprint?
You could do regular expression matching. A naive backtracking matcher can easily be pushed into exponential behavior on inputs that a smarter matcher can handle in linear time.