Here's a proof, from Wikipedia, that $K_6$ has at least 2 monochromatic triangles. You may find that this method of proof generalizes to give you the lower bound you want.
"An alternate proof works by double counting. It goes as follows: Count the number of ordered triples of vertices $x, y, z$ such that the edge $(xy)$ is red and the edge $(yz)$ is blue. Firstly, any given vertex will be the middle of either $0\times5=0$ (all edges from the vertex are the same color), $1\times4=4$ (four are the same color, one is the other color), or $2\times3=6$ (three are the same color, two are the other color) such triples. Therefore there are at most $6\times6=36$ such triples. Secondly, for any non-monochromatic triangle $(xyz)$, there exist precisely two such triples. Therefore there are at most 18 non-monochromatic triangles. Therefore at least 2 of the 20 triangles in the $K_6$ are monochromatic."
On the other hand, if you want all the work done for you, there is an answer in A W Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959) 778-783, also in Frank Harary, The two-triangle case of the acquaintance graph, Math. Mag. 45 (1972) 130-135.
We know that $N(3,4;2)=9$. By symmetry, we have that $N(4,3;2)=9$.
Thus we have the following: $
\lbrack
N(4,4;2)\leq N(3,4;2)+N(4,3;2)=18
\rbrack
$
Thus we create a counterexample, $K_{17}$ that does not contain any
red $K_{4}$ or green $K_{4}$. To do this, we label the vertices
$v_{1}=1,\dots,v_{17}=17$. Then we take all edges, $(v_{i},v_{j})$
with $i-j\equiv\pm1,2,4\text{or}8$ to be red. First off, it is easy
to show that the only 3 node closed paths that can be formed are by
the vertices $T_{1}=\{v_{i},v_{i+1},v_{i+2}\}$ or $T_{2}=\{v_{i},v_{i+4},v_{i+8}\}$,
or $T_{3}=\{v_{i},v_{i+2},v_{i+4}\}$ (i.e. sequences $i_{1},i_{2},i_{3}$
whose elements differ by $1,2,4,\text{or}8$), or some $T$ containing
permutations of these nodes. Thus in order to form $K_{4}$ from one
of these triangles, we must be able to find a vertex $v_{i_{4}}$
such that $v_{i_{4}}$ is connected to each $v_{i_{1}},\dots,v_{i_{3}}$(i.e.
each 3-shuffle of any of the 4 vertices: $(v_{i_{j_{1}}},\dots v_{i_{j_{3}}})$
should contain a triangle, and thus $v_{i_{4}}$ such form a triangle
with each of the other $v_{i_{j}}$. However, looking at the available
triangles, we find that this is impossible. E.g. for $T_{1}$, adding
a $v_{\ell}$ would not produce a triangle between $\{v_{i},v_{i+1},v_{\ell}\}$
for $\ell=i+4$, $i-4$, $i+8$, $i-8$. The same holds for $T_{2}$,
$T_{3}$ for similar reasons.
Now we look at the set of green edges (the edges $(v_{i},v_{j})$
with $i-j\equiv3,5,6,7$). (note that we do not include $9$ because
in this situation, a difference of $8$ is equivalent to a difference
of $9$ by symmetry of the graph. We can only have the following triangles
$T_{1}=\{v_{i},v_{i+3},v_{i+6}\}$, $T_{2}=\{v_{i-5},v_{i},v_{i+7}\}$
since $-12\bmod17=5$, and $T_{3}=\{v_{i-5},v_{i},v_{i+6}\}$
for similar reasons. However, by the same reasoning above, we cannot
form $K_{4}$ from these triangles using the available vertices and
edges. E.g. For $T_{1}$, we cannot add $v_{i-5}$ (because $\{v_{i-5},v_{i},v_{i+3}\}$
is not an available triangle) or $v_{i+5}$ or $v_{i-7}$ or $v_{i+7}$
for similar reasons. Thus we see that we cannot form a red or green
$K_{4}$ in this counter example, so we have shown that
\begin{eqnarray*}
N(4,4;2) & \nless & 18\implies\\
N(4,4;2) & = & 18
\end{eqnarray*}
Best Answer
Let $Y$ be the number of triangles in $G$, let $Z$ be the number of copies of $K_t$ with no edge in $G$, and let $X = Y + Z$. As you have observed, by linearity of expectation, $$ E(X) = E(Y) + E(Z) = {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t. $$
The key is that, with positive probability, $X \leq E(X)$. Hence, there exists $G \in \mathcal G(n,p)$ such that $X \leq {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t$. Now you have a specific graph to which you can apply the vertex-deletion process that you described.
At this point, it's enough to show that there exists a positive constant $c$ such that for all $t \geq 3$, there exist $n$ and $p$ such that $$ n - {{n}\choose{3}}p^3 - {{n}\choose{t}}(1-p)^t \geq c \biggl(\frac{t}{\log t}\biggr)^{\frac{3}{2}}. \tag{1}\label{eq:R3tBound} $$ Here's a hint: Let $n = 2c\bigl(\frac{t}{\log t}\bigr)^{\frac{3}{2}}$. If $p$ is a function of $n$ (and hence of $t$) such that $$ {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t \leq c \biggl(\frac{t}{\log t}\biggr)^{\frac{3}{2}}, $$ then the desired inequality \eqref{eq:R3tBound} follows immediately.