With ttnphns nomenclature, I tested RGC, RP, and KMPP on:

- 2D/3D points
- bag of words from textual documents
- curves with essentially an $L^2$ distance.

I don't recommend RGC because the resulting centers are very close to each other: the mean of many points is close to the global mean (law of large numbers). This can slow down convergence a lot: it takes some time before clusters start to individualize.

RP is generally good and would recommand as the first easy choice.

KMPP is very popular and works very well on small datasets or small dimension: compared to RP it tends to reduce the probability of ending in a local minimum.

However when I was working on big datasets (1M points that are bag of words from textual documents), RP slightly outperformed KMPP in the sense that it ended with slightly fewer iterations. I was surprised of this. In big dataset/high dimension, the convergence to the global minimum is impossible, you measure quality as "how good the local minimum is" = "how small final SOD is". Both methods had the same quality.

Note that it is important to use a randomized method if you want to use replications to improve the quality.