I’m not sure there’s necessarily going to be a satisfying general answer to find here though. I can invent an NP-complete problem with very easy instances by combining a linear time problem with an NP-complete problem, e.g. “Does this list of cities have a complete route shorter than X OR is one of the cities New York?”
All of the “yes New York” solutions are easy, but there’s no deep, satisfying reason for that. It’s just a hard problem glued onto an easy problem. For all we know, a lot of NP-hard problems could be like that, and the structure of the easy instances could be essentially unrelated between problems.
