Can a natural graph problem be universally hard?
The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer. 

Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples


Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)
Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own
Hamiltonian Circuit: same as Hamiltonian path except some designated vertex is replaced with a certificate graph containing a Hamiltonian cycle
Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)
Vertex cover: the certificate is again encoded by a matching


We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).

Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.