K-means: What are some good ways to choose an efficient set of initial centroids?
An approach that yields more consistent results is K-means++.  This approach acknowledges that there is probably a better choice of initial centroid locations than simple random assignment. Specifically, K-means tends to perform better when centroids are seeded in such a way that doesn't clump them together in space. 

In short, the method is as follows:


Choose one of your data points at random as an initial centroid.
Calculate $D(x)$, the distance between your initial centroid and all other data points, $x$.
Choose your next centroid from the remaining datapoints with probability proportional to $D(x)^2$
Repeat until all centroids have been assigned.


Note: $D(x)$ should be updated as more centroids are added.  It should be set to be the distance between a data point and the nearest centroid.

You may also be interested to read this paper that proposes the method and describes its overall expected performance.