Objective function for stochastic optimization
First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number.

The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data.

If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one.

The lower objective asks for "What's the expected error of the best $x$, in hindsight ", i.e. after we fix $A$, take the minimum over all $x$'s, and ask what's the error.
(more formally, for different $A$ values there are different "best" $x$s, so the each time take the best one for computing the error).

Since we are usually interested in finding the feature vector $x$ which explains the data, and not the expected error of the best $x$ after $A$ is fixed, the first stochastic objective makes more sense. The only reason I can think of as why would someone be interested in the second is for competitive-analysis like proofs (i.e. what's the gap between the best $x$ prior to knowing $A$ and the best one afterwards).