That is a good question :)
As mentioned in the comments, there are various decision problems which are NP-Hard (worst case complexity) while easy on average (average case complexity), for some distribution of instances!
The NP-Hardness concept is one of worst case complexity. Simplifying a bit, by definition a "Non-deterministic Polynomial time (NP)" algorithm which "decides" a NP Hard decision problem can be seen as a decision tree with an exponential fan-out (which is unavoidable unless P=NP) and a height (length of the longest branch) polynomial in the length of the input, where various instances lead to various leaves of such tree.
In most natural problems, most of the branches of this tree do not give an answer, forcing the algorithm to explore all the branches, which yield a running time exponential in the length of the input. But for some version of some problems (I give an example based on the parameterized version of the SATisfiability problem below), a constant fraction (e.g. half) of the branches yield a certified answer, which means that 1) a randomized algorithm has a constant probability to discover such branch (e.g. 1/2), and an expected running time corresponding to the traversal of a constant number of branches (e.g. within $O(1)$) instead of an exponential one; and 2) a deterministic algorithm running on a uniform distribution of instances will have a polynomial running time on average.
More generally, while many algorithms for NP Hard problem do not have a constant fraction of their branches leading to a useful certificate of the instance, if one 1) restricts the set of allowed instances and/or 2) skews the distribution of the instances so that to increase the probability to reach a usable certificate, the average complexity can become substantially smaller than the worst case complexity.
Concrete examples have been quite well documented by researchers working on the phase transition of the SATisfiability decision problem. Again, simplifying (more than) a bit, the SATisfiability decision problem is NP-Hard, but some observed that for some ranges of values of the ratio between the number of clauses and the number of variables, there are many value assignments to the variables which satisfy the formula, making such instances easy for randomized algorithms, or the average complexity of deterministic algorithms polynomial on average on such instances.
I did not know a good survey of such phase transition results, but this 2010 article seems to give a good overview, should you want to go beyond what I could summarize in a Stack Exchange post!
I hope it helps, take care!