In this paper, we prove that certain spaces are not quasi-isometric to Cayley graphs of finitely generated groups. In particular, we answer a question of Woess and prove a conjecture of Diestel and Leader by showing that certain homogeneous graphs are not quasi-isometric to a Cayley graph of a finitely generated group. This paper is the first in a sequence of papers proving results announced in [EFW0]. In particular, this paper contains many steps in the proofs of quasi-isometric rigidity of lattices in Sol and of the quasi-isometry classification of lamplighter groups. The proofs of those results are completed in [EFW1]. The method used here is based on the idea of coarse differentiation introduced in [EFW0].