Here's a proposed sketch of an approach. I hope it actually works... [EDIT: it doesn't, as it stands. I guess the main take-away from the rough outline below is that whatever the answer is for graphs should carry over to manifolds].
First, we can prove an appropriate analog in the category of graphs. Let $G$ be a base graph and $\tilde{G}$ a connected $m$-cover of $G$ in the combinatorial sense (the mapping takes vertices to vertices and edges to edges, and preserves local neighborhoods). It's useful to visualize $\tilde{G}$ this as a set of discrete fibers over the vertices of $G$, the vertices of which can be aribtrarily numbered $\{1,\ldots, m\}$. Now the edge-fibers correspond to permutations in $S_m$. Also notice that we may relabel the vertex fibers in order to make certain edge fibers "flat", meaning the corresponding permutation is the identity. This can simultaneously be done for a set of edges of $G$ which contain no cycle, such as a path (or a tree).
Given two vertices $\tilde{x}, \tilde{y}$ in $\tilde{G}$, there's a path $P$ of length at most $d$ between their projections $x,y$ in $G$. We may assume that the permutations over the edges in $P$ are trivial. A path from $\tilde{x}$ to $\tilde{y}$ can now be formed by navigating across the floors (at most $d$ steps in each trip [EDIT: could be worse, since as you move to a new floor you're not guaranteed to land on the path]) and among the floors (at most $m$ steps overall), yielding $md+m$ steps in total. Sorry this is so vague but it's really quite simple if you draw a picture.
Now $m(d+1)$ is a bit too large (we want $md$) but this can't be helped in the category of graphs: for example, the hexagon (diameter 3) is a 2-cover of the triangle (diameter 1). But this is just because the triangle misrepresents the true diameter of the underlying geometry, which is really $3/2$. To resolve this nuisance, apply the procedure above to a fine subdivision of $G$ (and $\tilde{G}$), which make $d \to \infty$ and the ratio is brought back to the desired $m$.
Next, consider simplicial complexes of higher dimension. It seems to me that if $X$ is a sufficiently nice topological space triangluated by a simplicial complex $K$, then the diameter of $X$ can be well approximated by the diameter of the 1-skeleton of a sufficiently fine subdivision of $K$. Is this true? Given two points in $X$ and a long path between them, if the path is close to a PL one than this should be the case. I hope that if $X$ is not too pathological, its diameter is represented by a tame path.
Finally, I would hope that a general Riemannian manifold (or some other kind of space for which we need to prove this) can be effectively triangulated, although this extends beyond my off-the-top-of-my-head knowledge.
Can something like this work?