We can in fact, a corrollary from MTyson's post is that we can construct a graph $G$ isomorphic to a hypercube $H$ (where the vertices are the $d$-bit strings and two vertices are adjacent in $H$ if they differ in precisely one bit) such that *every* edge in $G$ has length at least $\sqrt{d-1}$ in this metric, and $G$ admits a Hamiltonian circuit where half the edges have length $\sqrt{d}$.

Vertex $(u_1,u_2,\ldots, u_d)$ is adjacent in $G$ to $(1-u_1,1-u_2,\ldots, 1-u_{i-1}, u_i, 1-u_{i+1}, \ldots, 1-u_d)$ for all $i=1,2,\ldots, d-1$, and then vertex $(u_1,u_2, \ldots, u_d)$ is also adjacent in $G$ to its opposite $\bar{u}= (1-u_1,1-u_2, \ldots, 1-u_d)$.

Then $G$ is indeed isomorphic to a hypercube $H$ and has all edges of length at least $\sqrt{d-1}$. Furthermore, as $H$ admits a Hamiltonian circuit that has all edges of the form $\{(u_1, u_2, \ldots, u_{d-1}, u_d), (u_1, u_2, \ldots, u_{d-1}, 1-u_d)\}$ (i.e., the vertices differ in precisely their last bit), it follows that $G$ admits a Hamiltonian circuit that has all edges $\{u,\bar{u}\}$.

One can also check that no Hamiltonian cycle can have longer length than
$2^{d-1}(\sqrt{d} + \sqrt{d-1})$. Indeed, for each vertex $u$, there is only one other vertex that is $\sqrt{d}$ distance from $u$. So this implies that the edges $\{e = \{u,v\}; ||u-v||_2 = \sqrt{d} \}$ form a matching. Thus only half of the edges $e$ in a Hamiltonian cycle can have length $\sqrt{d}$, the remaining must have length no more than $\sqrt{d-1}$, giving the upper bound.

simplepath through hypercube corners. $\endgroup$ – Joseph O'Rourke Apr 15 '18 at 15:58