The maximal lottery is a voting system based on choosing an optimal candidate game-theoretically. If a winner isn't clear (there is no condorcet winner), then it will return probabilities as to which candidate is chosen.
Since it is based on the equilibrium zero-sum game, any other voting system will be, in retrospect, not better. Specifically, maximal lottery will have at least as many people who prefer its candidates over the candidates of other lotteries than vice-versa, on average.
My question is, why, at an intuitive level, it needs to be stochastic. What reason would we want this to be stochastic?
Since the payoff matrix used to define the maximal lottery is defined such that voting systems correspond to strategies in the corresponding game and a voting system is preferred over another on average precisely if it wins the game, you're effectively asking why there are zero-sum two-player games without pure Nash equilibria. Perhaps the simplest example of such a game is the game of matching pennies. Another example is afforded by the payoff matrix that occurs in my answer to your other question,
$$ \pmatrix{0&1&-1\\-1&0&1\\1&-1&0}\;, $$
corresponding to cyclically symmetrical preferences $1\gt2\gt3$, $2\gt3\gt1$ and $3\gt1\gt2$. By symmetry, this has a mixed Nash equilibrium at $\left(\frac13,\frac13,\frac13\right)$, and there are no other Nash equilibria, so in particular no pure ones.
By the definition of a Nash equilibrium, that means that for any other strategy, so in particular for any pure strategy, there's some other strategy whose candidates are on average preferred to that strategy's candidates. For instance the pure strategy that elects candidate $1$ is preferred by $2$ voters over the pure strategy that elects candidate $2$, and likewise for $2$ over $3$ and for $3$ over $1$. Thus, we have a rock-paper-scissors situation in which each of the pure strategies, and thus any deterministic voting system, is beaten by another one. As the existence of a Nash equilibrium is only guaranteed if we allow mixed strategies and a maximally preferred candidate selection corresponds to a Nash equilibrium, a maximally preferred candidate selection is only guaranteed if we allow randomization.