Nonisomorphic groups can have very similar multiplication (Cayley) tables. For example, the two groups
\begin{align*} \mathbb{Z}/9\mathbb{Z}&=\{\overset{a}{0},\overset{b}{1},\overset{c}{2},\overset{d}{3},\overset{e}{4},\overset{f}{5},\overset{g}{6},\overset{h}{7},\overset{i}{8}\}\\ \mathbb{Z}/3\mathbb{Z}\times\mathbb{Z}/3\mathbb{Z}&=\{\underset{a}{(0,0)},\underset{b}{(0,1)},\underset{i}{(0,2)},\underset{d}{(1,0)},\underset{e}{(1,1)},\underset{c}{(1,2)},\underset{g}{(2,0)},\underset{h}{(2,1)},\underset{f}{(2,2)}\} \end{align*}
have multiplication (Cayley) tables
\begin{array}{r|ccccccccc} \mathbb{Z}/9\mathbb{Z}&a&b&c&d&e&f&g&h&i\\\hline a&a&b&c&d&e&f&g&h&i\\ b&b&c&d&e&f&g&h&i&a\\ c&c&d&e&f&g&h&i&a&b\\ d&d&e&f&g&h&i&a&b&c\\ e&e&f&g&h&i&a&b&c&d\\ f&f&g&h&i&a&b&c&d&e\\ g&g&h&i&a&b&c&d&e&f\\ h&h&i&a&b&c&d&e&f&g\\ i&i&a&b&c&d&e&f&g&h\\ \end{array}
and
\begin{array}{r|ccccccccc} \mathbb{Z}/3\mathbb{Z}\times\mathbb{Z}/3\mathbb{Z}&a&b&c&d&e&f&g&h&i\\\hline a&a&b&c&d&e&f&g&h&i\\ b&b&\boxed{i}&d&e&\boxed{c}&g&h&\boxed{f}&a\\ c&c&d&\boxed{h}&f&g&\boxed{b}&i&a&\boxed{e}\\ d&d&e&f&g&h&i&a&b&c\\ e&e&\boxed{c}&g&h&\boxed{f}&a&b&\boxed{i}&d\\ f&f&g&\boxed{b}&i&a&\boxed{e}&c&d&\boxed{h}\\ g&g&h&i&a&b&c&d&e&f\\ h&h&\boxed{f}&a&b&\boxed{i}&d&e&\boxed{c}&g\\ i&i&a&\boxed{e}&c&d&\boxed{h}&f&g&\boxed{b}\\ \end{array}
respectively (note the boxed elements are different). The proportion of different elements between these two tables is $\frac{18}{9\times 9}=\frac{2}{9}\approx 22.2\%$.
Given a finite group $G=\{g_1\ldots g_n\}$ with a fixed enumeration of its elements, we define its multiplication table to be the unique matrix $M_G\in\{1\ldots n\}^{n\times n}$ such that for all $i,j\le n$, if $k=(M_G)_{ij}$ then $g_i\cdot g_j=g_k$.
Question.
Given $\varepsilon=\frac{1}{1000}$, does there exist two finite groups $G=\{g_1\ldots g_n\},H=\{h_1\ldots h_n\}$ with multiplication tables $M_G,M_H$, such that for all but at most $\varepsilon n^2$ many pairs $(i,j)\in\{1\ldots n\}^2$, it holds that $(M_G)_{ij}=(M_H)_{ij}$, and $G\not\cong H$?
Thanks for your help.
$\newcommand{\PP}{\mathbb{P}}$ I think I can show something like
Proposition: If two groups $G$ and $H$ on $[n]$ share more than $5 / 6$ of elements in their multiplication table, then $G \cong H$.
Proof: Let $g(i, j)$ denote the multiplication in $G$, and $h(i, j)$ denote the multiplication in $H$. By $\PP_{i,j}$, I mean sampling $i,j$ independently and uniformly from $[n]$ at random.
The first observation is
Lemma: for any $i \in [n]$, there exists a $\phi(i) \in [n]$ such that, for more than $2/3$-fraction of $k \in [n]$, we have $g(i, k) = h(\phi(i), k)$.
Proof: We sample $k, a$ uniformly and independently at random from $[n]$, and let $b$ satisfy $i = g(a, b)$. We estimate $$\PP_{a, k}(g(a, g(b, k)) \neq h(a, h(b, k))).$$ Note that if both $g(b, k) = h(b, k)$ and $g(a, g(b, k)) = h(a, g(b, k))$ holds, then we have $$h(a, h(b, k))) = h(a, g(b, k))) = g(a, g(b, k)).$$ So by the union bound, we have $$\PP_{a, k}(g(a, g(b, k)) \neq h(a, h(b, k))) \leq \PP_{a, k}(g(b, k) \neq h(b, k)) + \PP_{a, k}(g(a, g(b, k)) \neq h(a, g(b, k))).$$ The first term is less than $1/6$ by the multiplication table assumption. Now note that the joint distribution of $(a, g(b, k))$ is also uniform and independent from $[n]$, so we have $$\PP_{a, k}(g(a, g(b, k)) \neq h(a, g(b, k))) = \PP_{a, k}(g(a, k) \neq h(a, k)) < 1/6.$$ Thus, we have $$\PP_{a, k}(g(a, g(b, k)) \neq h(a, h(b, k))) < 1/3.$$ So there exists some $a$ such that $$\PP_{k}(g(a, g(b, k)) \neq h(a, h(b, k))) < 1/3.$$ By associativity, we have $$\PP_{k}(g(g(a, b), k) \neq h(h(a,b), k)) < 1/3.$$ Thus, $\phi(i) = h(a, b)$ has the desired property. $\square$
Now we observe
Lemma: $\phi$ is a group homomorphism.
Proof: It suffices to show that, for any $i, j \in [n]$ $$h(\phi(i), \phi(j)) = \phi(g(i, j)).$$ Pick $k \in [n]$ uniformly at random. We consider the probability $$\PP_k(g(g(i, j), k) \neq h(h(\phi(i), \phi(j)), k)).$$ If $g(j, k) = h(\phi(j), k)$ and $g(i, g(j, k)) = h(\phi(i), g(j, k))$, then $$g(g(i, j), k) = g(i, g(j, k)) = h(\phi(i), g(j, k)) = h(\phi(i), h(\phi(j), k)) = h(h(\phi(i), \phi(j)), k).$$ So $$\PP_k(g(g(i, j), k) \neq h(h(\phi(i), \phi(j)), k)) \leq \PP_k(g(j, k) \neq h(\phi(j), k)) + \PP_k(g(i, g(j, k)) \neq h(\phi(i), g(j, k))).$$ Again, $g(j, k)$ is uniformly distributed in $[n]$, so by the previous lemma, both summands are less than $1/3$. So we have $$\PP_k(g(g(i, j), k) \neq h(h(\phi(i), \phi(j)), k)) < 2/3.$$ On the other hand $$\PP_k(g(g(i, j), k) \neq h(\phi(g(i, j)), k)) < 1/3.$$ So there exists some $k \in [n]$ such that both $$g(g(i, j), k) = h(h(\phi(i), \phi(j)), k))$$ and $$g(g(i, j), k) = h(\phi(g(i, j)), k)$$ holds. This implies that $ h(h(\phi(i), \phi(j)), k)) = h(\phi(g(i, j)), k)$, so $h(\phi(i), \phi(j)) = \phi(g(i, j))$, as desired.
Finally, it suffices to show that $\phi$ is injective. Indeed, if $\phi(i) = \phi(j)$, then $$g(i, k) = h(\phi(i), k) = h(\phi(j), k) = g(j, k)$$ for at least $1/3$-fraction of $k$, so $i = j$. Thus, $\phi$ is a group isomorphism as desired.