How many colors do we need to avoid bichromatic triangles?

Problems of this variety have been studied, beginning with a paper of Erdős and Gyárfás, 'A variant of the classical Ramsey problem'. In that paper, they define a function $f(n,p,q)$ to be the smallest number of colours $k$ needed to produce a $k$-colouring of the edges of $K_n$ such that every $K_p$ contains at least $q$ distinct colours. The study of this function and its variants (such as replacing $K_p$ with a general graph $H$) leads to a great number of interesting questions. For example, even the behaviour of $f(n,4,3)$ is poorly understood.

As for $triR_k(K_{3,3})$, I would assume that the usual `averaging' approach should give an estimate not far from the optimal one. Take three colors with the maximal number of edges in them and estimate the number of triples of vertices having a common neighbour by these colors. If this number exceeds $2{n\choose 3}$, we are done. [EDIT] This seems to be covered by the Kővári–Sós–Turán theorem, see https://en.wikipedia.org/wiki/Zarankiewicz_problem. [END EDIT]

Exactly on the described situation, it seems that you have no chance for finding $K_{3,3}$ even in a complete graph with $n$ vertices and $n$-colored edges. Indeed, if we take a regular $(6k+1)$-gon and paint all parallel edges in one color, then the resulting graph would not contain a trichromatic $K_{3,3}$. Moreover, it seems that here we have some regularity which helps finding such $K_{3,3}$...

Regarding the question in "Motivation": a $1$-factorization of $K_{n,n}$ is essentially an $n\times n$ Latin square, and a $3$-chromatic $K_{3,3}$ would be a proper Latin subsqare.

This paper shows that there are Latin $n\times n$ squares with no proper Latin subsquares for $n=pq \neq 6$ where $p,q$ are distinct primes. The author claims that for $n$ prime it is well known that the multiplication table of the group of order $p$ is a Latin square with no proper Latin subsquares. Indeed, a proper Latin subsquare would correspond to a nontrivial proper subgroup.

Constructions of Latin $n\times n$ squares with no proper Latin subsquares are known for all odd $n$: http://www.sciencedirect.com/science/article/pii/S0195669805000909