This problem is co-NP-complete already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into an antichain $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
The complement of every pair is contained in $A$ regardless of $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i\notin S$ and false if $i'\notin S$, otherwise arbitrarily. This definition is indeed correct, as $\overline{ii'}\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.

Remark. Originally I claimed this to be a full solution, but that was false, as shown by Emil in the comments. However, this argument proves the following weaker version.

I can prove that it is co-NP-complete to decide for an input family $A$ whether there is a set $S$ that is unrelated to all sets in $A$. I'll call such families maximal. This shows that any possible polynomial time algorithm must exploit that the input family is an antichain, already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into a family $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
The complement of every pair is contained in $A$ regardless of $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i\notin S$ and false if $i'\notin S$, otherwise arbitrarily. This definition is indeed correct, as $\overline{ii'}\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.

This problem is co-NP-complete already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into an antichain $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
Every pair is contained in $A$ regardless of $\Psi$, so $11'\in A$, $22'\in A$, ..., $nn'\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i'\in S$ and false if $i\in S$, otherwise arbitrarily. This definition is indeed correct, as $ii'\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.

This problem is co-NP-complete already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into an antichain $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
The complement of every pair is contained in $A$ regardless of $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i\notin S$ and false if $i'\notin S$, otherwise arbitrarily. This definition is indeed correct, as $\overline{ii'}\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.