We derive optimal-order homogenization rates for random nonlinear elliptic PDEs with monotone nonlinearity in the uniformly elliptic case. More precisely, for a random monotone operator on R-d with stationary law (that is spatially homogeneous statistics) and fast decay of correlations on scales larger than themicroscale epsilon > 0, we establish homogenization error estimates of the order e in case d >= 3, and of the order epsilon vertical bar log epsilon vertical bar(1/2) in case d = 2. Previous results in nonlinear stochastic homogenization have been limited to a small algebraic rate of convergence epsilon(delta). We also establish error estimates for the approximation of the homogenized operator by the method of representative volumes of the order (L/epsilon)(-d/2) for a representative volume of size L. Our results also hold in the case of systems for which a (small-scale) C-1,C-alpha regularity theory is available.