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:

$00)$ The set $S_{00}$ is horizontally finite and vertically finite in $(A\setminus X)\times (A\setminus Y)$;

$01)$ The set $S_{01}$ is horizontally finite and vertically cofinite in $(A\setminus X)\times Y$;

$10)$ The set $S_{10}$ is horizontally cofinite and vertically finite in $X\times (A\setminus Y)$;

$11)$ The set $S_{11}$ is horizontally cofinite and vertically cofinite in $X\times Y$.

**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.

First observe that every set $S\subseteq X\times Y$ can be thought as a multivalued function assigning to each $x\in X$ the set $S(x)=\{y\in Y:(x,y)\in S\}$. 

Under such description, sets $S\subseteq X\times Y$ which are horizontally finite and vertically finite correspond to finite-valued functions $S:X\multimap Y$ whose inverse $S^{-1}:Y\multimap X$ are also finite-valued.

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$.