The answer is $n-m+1$. We show this is always possible by induction on $n$. If $n = 1$, then we also have $m = 1$ and we can clearly color the only column red. This does the base case. Suppose we know the problem is true for $n-1$ and we have an arbitrary $m \times n$ board $B$. There are two cases: Case 1: In $B$ there exists two rows which are the same save for in one column. This column cannot be colored red, so erase it. Then throw out one of the two rows arbitrarily. Additionally, if any other pair of rows were made the same by erasing that column, arbitrarily throw out one of them too. This gets a board with $n-1$ columns and at most $m-1$ rows. By the induction hypothesis, we can get $n-m+1$ red columns in this reduced board. It is also valid to shade these same $n-m+1$ in the original board $B$, finishing this case. Case 2: In $B$ any pair of rows differs in at least two columns. This means it is valid to color any single column red; choose one arbitrarily and do so. The remainder of the board has dimensions $m \times (n-1)$. If $m \leq n-1$, then the induction hypothesis applies and we can get $n-m$ more red columns, which is all we need. Otherwise, $m = n$ and we only needed to shade one red column, which we already did. To show that this is the best possible, consider the board in which the black squares are those whose row index is greater than the column index (aka all squares below a 45 degree diagonal line from a corner). It is easy to check that shading any of the first $m-1$ columns would make two rows the same. So at most $n-(m-1) = n-m+1$ columns can be shaded.

A classical problem (although slightly re-worded); also featured in an old book by Ross Honsberger. There exists an alternative solution, using graph theoretical methods, but induction is most straightforward.