Your definitions imply that all horizontal sections of $S$ are almost equal and all vertical sections of $S$ are almost equal. The almost equality $X=^* Y$ of two sets $X,Y$ means that $X\Delta Y$ is finite. This implies that there exist some sets $X,Y\subseteq A$ such that $\{a\in A:(x,a)\in S\}=^*Y$ and $\{a\in A:(a,y)\in S\}=^*X$ for every $x,y\in A$.

Now to understand a possible structure of $S$ you should analyze the structure of the intersections $S_{11}=S\cap (X\times Y)$, $S_{01}=S\cap ((A\setminus X)\times Y)$, $S_{10}=S\cap (X\times (A\setminus Y))$ and $S_{00}=S\cap ((A\setminus X)\times(A\setminus Y))$.

The set $S$ satisfies your condition if and only if it satisfies the following four conditions:

Definition. A $S\subseteq X\times Y$ is called

$\bullet$ horizontally finite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\in S\}$ is finite;

$\bullet$ horizontally cofinite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\notin S\}$ is finite;

$\bullet$ vertically finite in $X\times Y$ if for every $x\in X$ the set $\{y\in Y:(x,y)\in S\}$ is finite;

$\bullet$ vertically cofinite in $X\times Y$ if for every $x\in X$ the set $\{y\in X:(x,y)\notin S\}$ is finite.

It remains to describe the structure of sets which are horizontally (co)finite and vertically (co)finite in Cartesian products.

Sets $S\subseteq X\times Y$ which are horizontally cofinite and vertically finite correspond to finite-valued functions $S:X\multimap Y$ such that for every $y\in Y$ the set $\{x\in X:y\notin S(x)\}$ is finite. In this case $|Y|\le \max\{\omega,|X|\}$.

If $X=Y=\omega$, then the multi-valued function $S$ can be described using the order properties of $\omega$.

In particular, $S\subseteq\omega\times\omega$ is horizontally and vertically finite if and only if there exist two non-decreasing unbounded functions $f,F:\omega\to\omega$ such that $S(x)\subseteq[f(x),F(x)]$ for all $x\in\omega$.

A set $S\subseteq\omega\times\omega$ is vertically finite and horizontally cofinite if and only if there exists two nondecreasing unbounded functions $f,F:\omega\to\omega$ such that $\{y\in\omega:y<f(x)\}\subseteq S(x)\subseteq\{y\in\omega:y<F(x)\}$ for all $x\in\omega$.

At first, let us introduce some relevant definitions.

Definition. A $S\subseteq X\times Y$ is called

$\bullet$ horizontally finite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\in S\}$ is finite;

$\bullet$ horizontally cofinite in $X\times Y$ if for every $y\in Y$ the set $\{x\in X:(x,y)\notin S\}$ is finite;

$\bullet$ vertically finite in $X\times Y$ if for every $x\in X$ the set $\{y\in Y:(x,y)\in S\}$ is finite;

$\bullet$ vertically cofinite in $X\times Y$ if for every $x\in X$ the set $\{y\in X:(x,y)\notin S\}$ is finite.

Proposition 1. Is a set $S\subseteq X\times Y$ is horizontally cofinite and vertically finite, then either $X$ is finite or $Y$ is finite or else $X$ and $Y$ are countable.

Proof. Assume that the sets $X$ and $Y$ are infinite. Choose any countably infinite set $C\subseteq Y$. Since $S$ is horizontally cofinite, for every $y\in C$ the set $S^{-1}(y)=\{x\in X:(x,y)\in S\}$ is cofinite in $X$. Assuming that $X$ is uncountable, we can find an element $x\in \bigcap_{y\in C}S^{-1}(y)$. For this element the set $S(x)=\{y\in Y:(x,y)\in S\}$ contains $C$ and hence is infinite, which contradicts the vertical finiteness of $S$. This contradiction shows that the set $X$ is countable. Then the set $\bigcup_{x\in X}S(x)$ is countable too. Assuming that $Y$ is uncountable, we can find a point $y\in Y\setminus\bigcup_{x\in X}S(x)$, for which the set $S^{-1}(y)=\emptyset$ is not cofinite in $X$. This contradiction shows that the set $Y$ is countable. $\square$

Now take any set $S\subseteq A\times A$ such that all horizontal sections of $S$ are almost equal and all vertical sections of $S$ are almost equal. The almost equality $X=^* Y$ of two sets $X,Y$ means that $X\Delta Y$ is finite. This implies that there exist some sets $X,Y\subseteq A$ such that $\{a\in A:(x,a)\in S\}=^*Y$ and $\{a\in A:(a,y)\in S\}=^*X$ for every $x,y\in A$. Moreover, we can assume that

$\bullet$ $X=\emptyset$ if $X$ is finite;

$\bullet$ $X=A$ if $X\setminus A$ is finite;

$\bullet$ $Y=\emptyset$ if $Y$ is finite;

$\bullet$ $Y=A$ if $X\setminus A$ is finite.

Now to understand a possible structure of $S$ we should analyze the structure of the intersections $S_{11}=S\cap (X\times Y)$, $S_{01}=S\cap ((A\setminus X)\times Y)$, $S_{10}=S\cap (X\times (A\setminus Y))$ and $S_{00}=S\cap ((A\setminus X)\times(A\setminus Y))$.

The set $S$ satisfies the condition from the problem if and only if it satisfies the following four conditions:

Proposition 2. If the set $A$ is uncountable, then $X=Y\in\{\emptyset,A\}$.

Proof. First we show that $X\in\{\emptyset,A\}$. Assuming that $X\notin\{\emptyset,A\}$, we conclude that the sets $X$ and $A\setminus X$ are infinite, by the choice of the set $X$. Since $A$ is uncountable, either $X$ or $A\setminus X$ is uncountable. If $X$ is uncountable, then the condition (10) and Proposition 1 ensure that the set $A\setminus Y$ is finite and hence $Y$ is uncountable. Applying Proposition 1 to the condition (01), we conclude that the set $A\setminus X$ is finite, which contradicts our assumption. If $A\setminus X$ is uncountable, then we can apply Proposition to the condition (01) and conclude that $Y$ is finite and hence $A\setminus Y$ is uncountable. In this case we can apply Proposition 1 to the condition (10) and conclude that the set $X$ is finite, which contradicts our assumption. This contradiction shows that $X\in\{\emptyset,A\}$.

By analogy we can show that $Y\in\{\emptyset,A\}$.

Assuming that $X\ne Y$, we conclude that either $X=\emptyset$ and $Y=A$ or else $X=A$ and $Y=\emptyset$.

First we consider case $X=A$ and $Y=\emptyset$. In this case the set $S$ is horizontally cofinite and vertically finite in $A\times A$. By Proposition 1, $A$ is finite or countable, which is not the case. By analogy we can derive a constradiction assuming that $X=\emptyset$ and $Y=A$. This contradiction shows that $X=Y\in\{\emptyset,A\}$ and completes the proof. $\square$

It remains to analyze the structure of the set $S$ in case of countably infinite set $A$, which can be identified with $\omega$.

In particular, $S\subseteq\omega\times\omega$ is horizontally and vertically finite if and only if there exist two non-decreasing unbounded functions $f,F:\omega\to\omega$ such that $S(x)\subseteq[f(x),F(x)]$ for all $x\in\omega$.

On the other hand, a set $S\subseteq\omega\times\omega$ is vertically finite and horizontally cofinite if and only if there exists two nondecreasing unbounded functions $f,F:\omega\to\omega$ such that $\{y\in\omega:y<f(x)\}\subseteq S(x)\subseteq\{y\in\omega:y<F(x)\}$ for all $x\in\omega$.