You don't state this explicitly, but from your description of the problem it seems likely that you're after a high-biased set of quantiles (e.g., 50th, 90th, 95th and 99th percentiles).
If that's the case, I've had a lot of success with the method described in "Effective Computation of Biased Quantiles over Data Streams" by Cormode et al. It's a fast algorithm that requires little memory and that's easy to implement.
The method is based on an earlier algorithm by Greenwald and Khanna that maintains a small sample of the input stream along with upper and lower bounds on the rank of the values in the sample. It requires more space than a collection of few moments, but will be much better at describing the interesting tail region of the distribution accurately.