Let $L$ be a language consisting of a binary relation symbol $R$. Consider the following $L$-structures on $\mathbb N$:
$\mathcal N_1=(\mathbb N, \equiv_2),\quad \mathcal N_2=(\mathbb N,<),\quad\mathcal N_3=(\mathbb N,|),\quad\mathcal N_4=(\mathbb N,E)$
where $m\equiv_2 n$ iff $2|m-n$, $<$ is the usual ordering of natural numbers, $|$ is the usual divisibility relation, and $mEn$ iff $m$ and $n$ are consecutive and the smaller one is even. Show that any two of these structures are not elementarily equivalent to each other.
My attempt:
Definition: $\mathcal M \equiv \mathcal N$ if for every $L$-sentence $\sigma$, we have $\mathcal M\models \sigma \iff \mathcal N\models \sigma$
Take $\mathcal N_1 $ and $\mathcal N_2$:
Let $\varphi:=\exists x \exists y(x=3 \, \wedge \, y=4)$
Now, $\mathcal N_1 \nvDash \varphi$ since $2\nmid 3-4$ but $\mathcal N_2 \models \varphi$ since $3<4$.
So, they are not elementarily equivalent to each other.
I don't know how else argue this.
Since your language has no constants you cannot use $3$ or $4$ the way you did there. By finding a sentence that is valid in one but not in other structure, these two structures shall not be elementarily equivalent.
First, observe that $\mathcal N_1$ and $\mathcal N_4$ satisfy the symmetric property, whereas $\mathcal N_2$ and $\mathcal N_3$ do not. Fortunately, this property can be expressed in this language as the sentence $\varphi:= \forall x\forall y\, xRy \to yRx$. So, we only need to show that $\mathcal N_1$ and $\mathcal N_4$ are not elementarily equivalent and that $\mathcal N_2$ and $\mathcal N_3$ aren't either.
For $\mathcal N_1$ and $\mathcal N_4$, observe that $\mathcal N_1\models \exists x\exists y \forall z (zRx\vee zRy)$, i.e. there are two natural numbers that are not related with one another and such that any other number shall be related with one of them. It happens that $\mathcal N_4$ does not satisfy this sentence, by construction of the relation $E$. (this part has been edited following the very useful comment by @Mark Kamsma)
It only remains to be shown that $\mathcal N_2$ and $\mathcal N_3$ are not elementarily equivalent. To this end, observe that $\mathcal N_2$ is a total order while $\mathcal N_3$ is not. The total order formula in this language is $\psi:= \forall x\forall y\, xRy\vee yRx$; it happens that $\mathcal N_2\models \psi$ while $\mathcal N_3\nvDash \psi$.
I hope this helps.