Many algorithms designed to accelerate the fuzzy c-means (FCM) clustering algorithm randomly sample the data. Typically, no statistical method is used to estimate the subsample size, despite the impact subsample sizes have on speed and quality. This paper introduces two new accelerated algorithms, i.e., geometric progressive fuzzy c-means (GOFCM) and minimum sample estimate random fuzzy c-means (MSERFCM), that use a statistical method to estimate the subsample size. GOFCM, which is a variant of single-pass fuzzy c-means (SPFCM), also leverages progressive sampling. MSERFCM, which is a variant of random sampling plus extension fuzzy c-means, gains a speedup from improved initialization. A general, novel stopping criterion for accelerated clustering is introduced. The new algorithms are compared with FCM and four accelerated variants of FCM. GOFCM’s speedup was four–47 times that of FCM and faster than SPFCM on each of the six datasets that are used in the experiments. For five of the datasets, partitions were within 1% of those of FCM. MSERFCM’s speedup was five–26 times that of FCM and produced partitions within 3% of those of FCM on all datasets. A unique dataset, consisting of plankton images, exposed the strengths and weaknesses of many of the algorithms tested. It is shown that the new stopping criterion is effective in speeding up algorithms such as SPFCM and the final partitions are very close to those of FCM.