Deciding graph homomorphism
If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general property of "graphs whose core has bounded treewidth."

Grohe proves a converse: if the cores of the graphs in $\mathcal{G}$ have unbounded treewidth, then the homomorphism problem from $\mathcal{G}$ is not polynomial-time solvable (assuming $FPT\neq W[1]$). Therefore, if you restrict the left-hand side graph to Cayley graphs etc., then what matters is whether the cores have bounded treewidth.

http://dl.acm.org/authorize?951212

Note that this does not completely answer your question: in the result of Grohe, it is  assumed that the right-hand side graph is arbitrary. You seem to be interested in results where the right-hand side graph is also restricted to some specific class of graphs.