Optimization problems with good characterization, but no polynomial-time algorithm
In some technical sense you are asking whether $P = NP \cap coNP$.  Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$.  This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ and $g_x(y) = 1$
otherwise.  Now indeed we have $max_y f_x(y) = min_y g_x(y)$.

So in this sense, any problem known to be in $NP \cap coNP$ but not known to be in $P$ can be turned into an answer to your question.  E.g. Factoring (say, the decision version of whether the $i$'th bit of the largest factor is 1).