For instance the formula:
$\forall x\exists y :\text{GreaterThan}(y, x)$
Which indicates that $x$ is greater than $y$. Does it suffice to find one structure where this statement is untrue to prove that the statement is logically untrue?
An example would be then: $D = \{n | n \in\mathbb N\}$ So that
$\forall x\exists y :\text{GreaterThan}(y, 0)$
makes the formula untrue?
In case you change the interpretation of $\text{GreaterThan}$ to $y$ is greater than $x$, the formula becomes true, right?
If logically true means tautology and logically untrue means not a tautology then yes, it suffices to find one such structure. A formula $A$ in $L$ which is a tautology is true in any structure for $L$. This immediately follows from the definition of tautology (I'm using Shoenfield's terminology). However, it is easier to use the definition directly.
P.S. Also keep in mind that $\exists y :\text{GreaterThan}(y, 0)$ and $\text{GreaterThan}(y, 0)$ are not equivalent. You probably meant the first one in the second highlighted line.