The question is a little ambiguous as to what it is asking. But the idea is clear and it is a nice question. As I interpret it, I think the answer might be no and that designs and finite geometries might provide examples.

Since you want the guaranteed score ,not the expected one, I interpret your problem as this: We select some number $c$ of $k$ element subsets from an $N$ set, say $G_1,\cdots,G_c$. Call these guesses or groups. Then someone else, knowing our choices, gets to pick $t \geq 1$ $k$-element subsets $T_1,\cdots,T_t,$ the target(s). Our score is the maximum of $T_j \cap G_i$. With $c=\frac{N}k$ (if that is an integer) we can be sure of a score of $\lceil\frac{k}c\rceil.$ Then the question is to bound our best score if $c$ is a polynomial in the size of $M=\frac{N}k$.

A design theory question is "How large a collection of $k$-element blocks can be chosen from a set of size $N$ so that each pair has intersection no larger than $\mu?$" Given a highly optimal example we might consider taking some, most, or all but one, as guesses and then one (or all) of the rest as targets.

One ambiguity is how $k$ and $N$ grow relative to each other. In your example $k=20$ and $N=100.$ The question might be different for large $N$ and $k=\frac{N}5$ compared to $k=2\sqrt{N}.$ Another is if you are concerned with polynomial size with respect to $N$ or $M=\frac{N}k.$

Here is the base set for some examples I was thinking of:

There is a field $\mathbb{F}=\mathbb{F}_q$ with $q$ elements for $q$ a prime power. This is integers $\bmod q$ for $q$ a prime. The Affine geometry $AG(q,d)$ consists of the $N=q^d$ points $(x_1,\cdots,x_d)$ with $x_i \in \mathbb{F}$ with lines, planes and higher dimensional subspaces defined in the obvious way. In $AG(q,3)$ there are $q^3$ points, $q^4+q^3+q^2$ lines of size $q$ and $q^3+q^2+q$ planes with $q^2$ points.

An ovoid in $AG(q,3)$ is a subset of $q^2$ points, no three collinear. It turns out that these exist (for example the points $(s,t,s^2+st+at^2)$ where the polynomial $x^2+x+a$ does not factor in $\mathbb{F}$.) It turns out that exactly $q^2$ of the planes intersect the ovoid in a single point and the other $q^3+q$ intersect it in exactly $q^2$ points. (Note, ovoids are generally defined in a projective space, but I think I translated correctly)

I don't know that the $c=q^3+q^2+q$ planes are the optimal choice for that $c$ and $N=q^3, k=q^2.$ But it feels like they should be. Here $M=\frac{N}k=q$ so $c=O(M^3)$ and $\frac{k^2}N=q.$ If the target is an ovoid we have no improvement over the case $c=q$ of an arbitrary partition into $q$ groups.

I think there are $O(q^6)$ ovoids so we could take that many targets.

I suspect that we could take the guesses to be all the ovoids and the target to be a plane to have $c=O(M^6).$ Actually we could also throw all other planes into the guess collection. This would be nicer in a projective setting. I justify this by analogy below.

For $N=q^{d},k=q$ and $c=q^{d-1}\frac{q^d-1}{q-1}=O(M^2)$ , I don't know that the lines of $AG(q,d)$ are an optimal choice of guesses, but again it seems as if it should be. Then having the target be the set of points $(1,t,t^2,\cdots,t^{d-1})$ for $t \in \mathbb{F}$ does allow a score of $2$ while $\lceil \frac{k^2}N \rceil=\lceil \frac1{q^{2d-2}} \rceil=1.$

There might be other examples of this flavor.

An analogy for the first example with $\mathbb{R}^3$ is if the guesses are the planes and the target is a sphere. Then these are $2$ dimensional in a $3$ dimensional setting and the intersections are one dimensional (so $q^2,q^3$ and $q$ in some sense.) In that setting the collection of all ovoids $a(x-u)^2+b(y-v)^2+c(z-w)^2=1$ is $6$-dimensional. Then if the target is a plane the intersections will be one dimensional. I suspect this translates into an example over finite fields though I didn't check very carefully. If so, $N=q^3,k=q^2,c=O(M^6)$ and the score $q$ is no better than for $c=M.$