Lemma: Let $K_{m, n}$ be the complete bipartite graph on sets of vertices $A$ and $B$ with respective sizes $m$ and $n$. If the edges of $K_{m, n}$ are two-colored, then there is a monochromatic connected subgraph spanning at least $\frac{m+n}{2}$ vertices.
Proof: Call the colors red and blue. Call a vertex red-primary if it has more red than blue edges, blue-primary if it has more blue than red edges, and neutral if the numbers are equal. There are two cases.
Case 1. For some set $X \in \{A, B\}$ and for some color $C \in \{\text{red}, \text{blue}\}$, at least one vertex in $X$ is $C$-primary, and at least $|X|/2$ vertices in $X$ are either $C$-primary or neutral.
Suppose without loss of generality that $A$ has at least one red-primary vertex, and the majority of vertices in $A$ are red-primary or neutral. If $a_1 \in A$ is red-primary and $a_2$ is either red-primary or neutral, then by the pigeonhole principle, some vertex in $B$ has red edges to both $a_1$ and $a_2$. Thus, there is a red connected graph spanning at least any red-primary or neutral vertex in $A$ (which makes up at least half of $A$) and any vertex in $B$ with red edges to any of these vertices (which makes up at least half of $B$, as any single red-primary or neutral vertex has red connections to at least half of the other set).
Case 2. Every vertex is neutral. Then any vertex $A$ has red connections to exactly half the vertices of $B$. Each of those vertices has a red connection to exactly half of $A$ (perhaps a different half each time). This gives us a red monochromatic subgraph.
Now to the main problem. The cases $n = 1, 2, 3, 4$ can be established trivially. The required subgraph for $n = 2m-1$ odd is has the same size as that for $n = 2m$ even, so it suffices to prove the case for odd $n$.
We work by induction, showing that the claim for $n=2m-1$ implies the claim for $n=2m+1$. Let the colors be red, blue, and green, and let $K_{2m+1}$ be a complete edge-3-colored graph on $2m+1$ vertices. By the induction hypothesis, $K_{2m+1}$ has a connected monochromatic (without loss of generality, green) subgraph of $m$ vertices. Let $G$ be this set of vertices, and let $H$ be the rest of $K_{2m+1}$. If any of the edges from $G$ to $H$ is green, then we have a connected green graph of the required size $m+1$. Otherwise, erasing every edge internal to $G$ or to $H$ gives a complete bipartite graph on $m$ and $m+1$ vertices with every edge colored either red or blue, and the lemma guarantees either a red or a blue monochromatic subgraph with the required size.
Remark: It is possible to construct instances in which the given bound is tight. For example, for $n = 4m$ even, one may construct a graph with no monochromatic graph larger than $2n$ by taking four equally sized sets of vertexes $A, B, C, D$ and coloring all edges internal to the sets $A \cup B$ and $C \cup D$ green, edges from $A$ to $C$ or $B$ to $D$ red, and edges from $A$ to $D$ or $B$ to $C$ blue.
The complete graph $K_{14}$ is much bigger than needed for this result; here are three proper subgraphs with the same property.
I. Every $2$-coloring of the complete bipartite graph $K_{3,7}$ contains a monochromatic $C_4$.
Let $K_{3,7}$ have partite sets $V_1,V_2$ with $|V_1|=3$ and $|V_2|=7$. Each vertex in $V_2$ is joined by edges of one color to two vertices in $V_1$. By the pigeonhole principle, two vertices in $V_2$ are joined by edges of the same color to the same two vertices in $V_1$.
II. Every $2$-coloring of the complete graph $K_6$ contains a monochromatic $C_4$. (This was shown in Misha Lavrov's answer; the following argument is perhaps slightly simpler.)
We may assume that there is a vertex $x$ which is incident with at most two blue edges. In fact, we may assume that $x$ is incident with exactly two blue edges; otherwise $x$ would be incident with four red edges, call them $xa_1$, $xa_2$, $xa_3$, $xa_4$, and then we could consider a vertex $y\notin\{x,a_1,a_2,a_3,a_4\}$ and proceed as in paw88789's answer. (It may be even easier to observe that the subgraph induced by $\{a_1,a_2,a_3,a_4\}$ contains either a red $P_3$ or a blue $C_4$.)
So let $x$ be incident with exactly two blue edges, $xy$ and $xz$. If one of the remaining three vertices is joined by blue to both $y$ and $z$, then we have a blue $C_4$. On the other hand, if each of those three vertices is joined by red to a vertex in $\{y,z\}$, then two of them are joined by red to the same vertex in $\{y,z\}$, and also to $x$, making a red $C_4$.
III. Every $2$-coloring of the complete bipartite graph $K_{5,5}$ contains a monochromatic $C_4$.
The proof is left as an exercise for the reader.
Best Answer
Suppose $v_1$ and $v_2$ are vertices with no blue path of length at most $3$ joining them, and note that $v_1$ and $v_2$ are joined by a red edge.
Now consider the sets $V_{RB}=\{$ vertices joined by a red edge to $v_1$ and a blue edge to $v_2\}$, $V_{BR}=\{$ vertices joined by a blue edge to $v_1$ and a red edge to $v_2\}$, $V_{RR}=\{$ vertices joined by a red edge to both $v_1$ and $v_2\}$.
There are no vertices which are joined by blue edges to both $v_1$ and $v_2$, by the hypothesis, so every vertex is joined to both $v_1$ and $v_2$ either directly, by a red edge, or by a red path of length $2$ via the other.
Then any two vertices in the same one of these three sets are joined to each other by a red path of length $2$ (via either $v_1$ or $v_2$).
A vertex in $V_{RR}$ is joined to one in $V_{RB}$ or $V_{BR}$ by a red path of length 2 (via either $v_1$ or $v_2$).
Finally, any vertex in $V_{RB}$ is joined by a red edge to one in $V_{BR}$ - if the edge joining them were blue, there would be a blue path of length $3$ from $v_1$ to $v_2$ via these two vertices.
Hence, from the hypothesis that there is a pair of vertices with no blue path of length $3$ between them, we have shown that every pair of vertices is connected by a red path of length at most $3$.