Is the following statement correct?
Statement For every three numbers $A,B,C\in\mathbb N_+$, and for every two non-decreasing functions $f,g:\mathbb N_+\to\mathbb N_+$ that satisfy $f(n),g(n)\in O(n)$.
It holds that:
$\displaystyle\min_{a\in\{1,\dots,A\}\\b\in\{1,\dots,B\}}\bigg\{ \frac C {ab} \Big(f(a)+g(b)\Big)\bigg\}\geq \frac C {AB}(f(A)+g(B))$
This statement sounds to me true, but I can't figure out how to prove it formally.
The statement isn't true. For a concrete counterexample, set
$$A=B=2, C=1,$$
and
$$ f(n)=g(n) = \begin{cases} 1, & \text{ if } n=1 \\ 6, & \text{ if } n\ge 2. \\ \end{cases} $$
If we define for $a,b \in \mathbb N_+$ $$L(a,b) = \frac{C}{ab}\left(f(a) + g(b)\right),$$
then we have for the above stated $A,B,C,f(n),g(n)$:
$$L(1,1) = \frac11(1+1) = 2$$
and
$$L(A,B)=L(2,2) = \frac14(6+6)=3,$$
so obviuously
$$\min_{a\in\{1,\dots,A\}\\b\in\{1,\dots,B\}} L(a,b) < L(A,B),$$
in contradiction to the statement.
Generally, as stated in a comment by Cade Reinberger, $C$ is a multiplicative constant on both sides and because everything is positive, it can easily cancelled and need not be considered or just set to 1.
Also, in the problem statement as written, the $O(n)$ condition is more or less meaningless. By requiring the statement to be true for all $A,B$, you have opened the door for a counterexample of the type I gave, involving just small numbers.
Some avenues you might consider:
Setting C=1, as explained above, we have
$$L(a,b)=\frac{f(a)}a\frac1b+\frac{g(b)}b\frac1a$$
The $\frac1a$ and $\frac1b$ terms are obviously decreasing with increasing $a,b$. If you want the whole term to be non-increasing with increasing $a,b$, you could require that $\frac{f(a)}a$ and $\frac{g(b)}b$ be non-increasing, but that is a condition that is much stricter than requiring $f,g \in O(n)$.
If you want the $O(n)$ condition to be meaningful, then maybe you must require that the inequality doesn't hold for all $A,B$, but only for sufficiently large $A,B \ge M$, where $M$ depends on $f$ and $g$. But even then it is possible that you have big increasing jumps in $\frac{f(a)}a$ and $\frac{g(b)}b$, resp, even requiring $a,b \ge M$.