Bounds on "well dispersed" sparse matrices
The answer to the main question is yes, and the key to the construction is the notion of an expander graph.


  A (bipartite $d$-left-regular) expander graph between vertices $\mathcal{I}$ and $\mathcal{O}$ (the bipartition), where $|\mathcal{I}|=|\mathcal{O}|=n$, with expansion factor $c&gt;0$, is a graph which is $d$-left-regular, meaning that each $x\in \mathcal{I}$ has degree $d$, such that for all subsets $A\subseteq I$ such that $|A|\le n/2$, the set $B\subseteq\mathcal{O}$ of neighbors of elements of $A$ has $|B|\ge (1+c)|A|$.


There are many proofs of existence of expander graphs like this by the probabilistic method and some deterministic methods as well; for the present purpose we only need that expander graphs as defined above exist for some constant $c&gt;0$ independent of $n$.

Given such a graph, we can construct a $n\times n$ matrix from the adjacency matrix of the graph, with $\mathcal{I}$ for the rows and $\mathcal{O}$ for the columns. This matrix has exactly $k=dn=O(n)$ ones, because of the $d$ left regular property, and the expander property is unaffected by any permutations performed by the adversary.

Now for $\alpha&gt;0$, let $A$ be the last $\alpha n$ elements of $\mathcal{I}$ and let $C$ be the last $\alpha n$ elements of $\mathcal{O}$, after the adversary has chosen an ordering of the rows and columns. If there is no one in this square in the matrix, then there must correspondingly be no edge between $A$ and $C$, and hence the neighbors $B$ of elements of $A$ must satisfy $B\subseteq C^c$, so by the expander graph property this implies
$$(1+c)|A|=(1+c)\alpha n\le |B|\le |C^c|=(1-\alpha)n\implies \alpha\le\frac{1}{2+c}.$$

Thus any empty bottom right square must be smaller than $n/(2+c)\times n/(2+c)$, so in the language of the OP, $$f(n,k)\ge 2n\left(1-\frac{1}{2+c}\right)=(1+\epsilon)n$$
where $\epsilon=\dfrac{c}{2+c}&gt;0$.