As pointed out by Gerry Myerson, this has a lot to do with autocorrelation of a sequence. More specifically incomplete (or aperiodic) autocorrelation.
What I say below will give something non-trivial only when $m$ is relatively large in comparison to $n$.
As a typical example (also of a De Bruijn sequence as recalled by Gerhard Paseman) consider the so called $m$-sequence. Let $\alpha$ be a generator (aka a primitive element) of the multiplicative group of the finite field $GF(2^\ell)$. Let $tr$ be the trace function from $GF(2^\ell)$ to $GF(2)$. Then an $m$-sequence $s$ of length $n=2^\ell-1$ is gotten by the recipe $$ s(i)=tr(\alpha^i), i=0,1,\ldots,n-1. $$ As $\alpha$ is of order $n$, the sequence starts repeating periodically, so we don't need to be too picky about where we start.
As is commonly done here, we map the bits to real numbers $0\mapsto+1, 1\mapsto -1$, so that we can apply the techniques of character sums. In other words, let's denote by $e(x)=(-1)^{tr(x)}$ the resulting (additive) character of $GF(2^\ell)$.
Two subvectors of length $m$ are just initial fragments of various cyclic shifts of $s$. If we start two subvectors from indices $a$ and $b$ respectively, then their Hamming distance is $$ d(s_a,s_b)=\frac12\sum_{i=0}^{m-1}\left(1+(-1)^{s(a+i)+s(b+i)}\right)=\frac{m}2+\frac12\sum_{i=0}^{m-1}e((\alpha^a+\alpha^b)\alpha^i). $$ As $a\neq b$, here the constant (=independent of $i$) $\alpha^a+\alpha^b\neq0$.
To cut a long story short this is a type of an incomplete exponential sum, where the (Polya-)Vinogradov method works splendidly. This is largely because the DFT of the sequence $s$ consists of Gauss sums, so they are well bounded. The end result is that we get estimates of the order $O(\sqrt n \log n)$ for the incomplete sums. So if $m$ is large in comparison $\sqrt n\log n$, we get the result that the Hamming distances between the two is "about" $m/2$.
I had the (unfortunately somewhat questionable) pleasure of extending this type of results to larger families of Kasami sequences. Other similar extensions to e.g. 4-phase sequences and their binary Grey-image sequences have also been carried out. A group of coding theorists enjoyed a field day or three with these problems in the 90s.
The Vinogradov-method is not expected to give a very sharp bound. IIRC Philippe Langevin from Toulon, France, has collected a lot of numerical data on these incomplete sums.