One example that's familiar to many people is dishwasher loading. You have a set of items (3-dimensional objects) you want to fit in a dishwasher. Many people have experienced that greedy methods and heuristics don't work: you load up the dishwasher using some sensible method and things don't fit. But then if you start from scratch and load things slightly differently, there's plenty of room.
The dishwasher example is nice because it's relatively familiar, and gives some intuition about why NP hardness problems are really hard: fitting things nicely locally doesn't necessarily give a good global solution. It's also truly an NP-hard problem, even in very simple cases (like all your dishes are cubes).
It's obvious that an NP machine can solve dishwasher loading in polynomial time (as it can try all ways of loading the dishwasher non-deterministically). On the other hand, most natural NP-hard problems can be solved using something like this so I'm not sure if that's the structure you want.
A second example that's likely even more familiar is three-dimensional pathfinding. Many people have experienced the struggle of (say) trying to move a couch into a new apartment. 3-dimensional pathfinding Shortest path in three dimensions in general is NP-hard (see New Results on Shortest Paths in Three Dimensions by Mitchell and Sharir for example). Some disadvantages of this problem are that the technical aspect is more difficult, and that everyday cases are often easy. (Aside from moving couches into small apartments I solve 3-dimensional shortest path every day without much issue.)