Consider 19 columns with 4 cells each. Since we have 3 colors, at least 2 cells in each column have the same color. Let's call the main color of a column is the repeated color. Since we have 19 columns, one of the colors, say red, is the main color for at least 7 columns. So each of these 7 columns has at least 2 red colors. There are $4 \choose 2$$ = 6$ distinct ways of choosing these 2 red cells. As we have 7 columns, two of them will match and this will give us the required pairs of rows and columns.

Board has $4$ rows and $19$ columns. In each column there is a color used at least $2$ times in it. Since $19$$>$${4}\choose {2}$$\times 3$ we find that there is the same conficuration of $2$ same colors in $2$ different columns. Then there is a rectangle with same colored vertices. Then we are done!