This is not close to a complete answer, but for $m=2$, $n>>2$, and uniform random variables, the first option has a greater expected value. 

If you skip the first optimization and just look at the largest of $n$ IID random variables uniform on $[0,1]$, the expected maximum is $n/(n+1)$. The first optimization does not decrease this, so the expected value returned by the first method is at least $n/(n+1)$. 

The sums of the columns are distributed by the tent function supported on $[0,2]$. Conditioning on the maximum value of the sum of a column $v \gt 1$, the expected largest value in that column is $1/2 + v/4$, a linear function. The value is smaller, $3v/4$, in case the column has sum under $1$. The expected value of the second method is at most $1/2 + E(v_n)/4$ where $v_n$ is the maximum of $n$ IID samples from the tent function on $[0,2]$.

I believe $E(v_n)$ is roughly $2-\sqrt{\frac2 {n+1}}$, which would imply that the second method produces a value of about $1-\frac{1}{4}\sqrt{\frac{2}{n+1}}$ which is asymptotically smaller than $1-1/(n+1)$. A quick estimate which establishes the inequality for large $n$ is to note that the probability that the sum in a column is at most $2-\sqrt{\frac 2 {n+1}}$ is $\frac{n}{n+1}$, so the probability that the largest column sum is at most $2-\sqrt{\frac 2 {n+1}}$ is $(\frac{n}{n+1})^n \gt 1/e$. So, maximizing the columns first produces a value which is at most $1-\frac{1}{4e}\sqrt{\frac{2}{n+1}}$ which is asymptotically smaller than the lower bound for the expected value of the first method, $1-\frac{1}{n+1}$. 

In a quick numerical test for $m=2, ~n=100$, the first method gave a value of about $0.991$ and the second about $0.969$. For $m=2, ~n=3$, the first method gave $0.835$ and the second $0.829$.