The communication complexity of the distance between two strings
Suppose that the Hamming distance between $x$ and $y$ is $n/2 - \sqrt{n}$. Suppose that you sample $m$ indices with replacement, and let $S$ be the number of indices on which $x$ and $y$ disagree. Then $S$ has expectation $mp$ and variance $mp(1-p)$, where $p = 1/2 - 1/\sqrt{n}$. According to the central limit theorem, for every fixed $t$ we have
$$
\Pr\left[ \frac{S-mp}{\sqrt{mp(1-p)}} \leq t \right] \longrightarrow \Pr[N(0,1) \leq t].
$$
We are interested in the event $S \leq m/2$, which is the same as $S - mp \leq m(1/2-p) = m/\sqrt{n}$, or equivalently
$$
\frac{S-m/p}{\sqrt{mp(1-p)}} \leq \frac{1/2-p}{\sqrt{p(1-p)}} \sqrt{m} \approx \sqrt{\frac{m}{4n}}.
$$
In particular, if $m = cn$ then (following a short argument) the probability of error tends to
$$
\Pr[N(0,1) &gt; \sqrt{c/4}].
$$
For small enough $c$, this would be more than $1/3$, giving an $\Omega(n)$ lower bound for this version of your algorithm.

In your case, you choose indices without replacement. A similar argument works, using the central limit theorem for hypergeometric random variables, see for example Lahiri and Chatterjee, A Berry–Esseen theorem for hypergeometric random probabilities under minimal conditions, Theorem 2.1.