Assume we have a set $A \times A$ and a constant $a$.
What is the best upper bound one can get for a subset $I \subset A \times A$ s.t. $I$ does not contain a subset $B \times C$ s.t. $|B|$ and $|C| > |A|/a$?
It seems like you should be able to get a bound of $|A|^2/a$ or potentially even $(|A|/a)^2$ but I can't quite work it out.
This is actually a generalization of the question I care about, which is a bound for $A=S_n$, and $a = 2^{(n-4)/2}$ (so $|A|/a = n!/2^{(n-4)/2}$)
EDIT: One can visualize a tight set in the following manner: Consider an $|A|$ by $|A|$ grid. Select the first $|A|/a$ columns and rows. Adding any further value will violate our condition. This set has size:
$ 2|A|^2/a - (|A|/a)^2 = (|A|/a)^2(2a - 1) $
Thus our upper bound is greater than this value.
In general, this is known as the Zarankiewicz problem: what is the largest subgraph of the complete bipartite graph $K_{n,n}$ which does not contain a copy of $K_{t,t}$?
Much of the literature seems to be concerned with the asymptotics in the case that $t$ is fixed and $n \to\infty$, and indeed this regime is probably where the most interesting dynamics lie. By contrast, your question has $n/t$ "fixed" or at least very small compared to $t$.
For this large-$t$ scenario I think we can get a simple lower bound by probabilistic method: include each element of $[n]\times[n]$ independently with probability $p$, and compute the expected number of subsets of size $t\times t$ that are covered. If we calibrate $p$ so that the expected value is $<1$ then there must exist a subset of size $n^2p$ which completely avoids any rectangular sets of size $t\times t$.
[I'm choosing to gloss over a necessary calculation which shows that the subsets of size substantially smaller than $n^2p$ are much too infrequent to be the sole cause of the expectation being $<1$. So we should choose the expectation to be an extra bit less than $1$, or we could show that we can afford a few unwanted $t\times t$ subsets and then delete a corresponding number of elements from our set to eliminate those.]
The expected number of $t\times t$ subsets that are included in our random set is $p^{t^2} \binom{n}{t}^2$. For this to be $<1$ we need $p < \binom{n}{t}^{-2/t^2}$. Assuming that $n/t \to \infty$ we have that $$\binom{n}{t} = \frac{(n-o(n))^t}{t!},$$ and so $\binom{n}{t}^{1/t}$ is asymptotic to $ne/t$ provided also that $t \to \infty$. Both conditions hold in the case that you're primarily interested in. So then we can take $p \sim (ne/t)^{-2/t} \sim n^{-2/t}$, so that our winning subset can be asymptotically of size $n^{2-2/t}$. I believe this latter asymptotic (thanks to the extra $t$th root) also holds in the case that $n/t$ is constant, which is close to your stated question.
This lower bound is essentially "twice as far" from $n^2$ as the Kővári-Sós-Turán upper bound of $n^{2 - 1/t}$, which I suspect is pretty tight in the case you're interested in.
Now, back to your original formulation. In the case that $a$ is fixed and $|A| \to \infty$ this gives an asymptotic lower bound of $$|A|^2 \exp\big(-2 \frac{a \log |A|}{|A|}\big)$$ and a similar upper bound with the $-2$ replaced by $-1$. Both are asymptotic to $|A|^2$ for any fixed value of $a>0$, so the $|A|^2/a^2$ construction is not very close to optimal.
In the case where $a$ grows like $2^n$ and $|A|$ grows like $n!$, then $a \log |A|$ is still much smaller than $|A|$ so the exponent still converges to $0$ and we get a set of size asymptotic to $|A|^2$. In order for this not to occur, we would need $a$ to be of order at least $|A|/\log |A| = \Theta((n-1)!)$, which is quite a bit larger than $c^n$.