As noted on the scikit-learn mailing list the poor results of the liblinear can be cause by a low convergence tolerance but also by the fact that the internal memory layout used by liblinear is not optimized for dense input data arrays as is the case for the SGDClassifier of scikit-learn.
Interesting comparison, but only using generated mixtures of gaussians for training data severely limits any conclusions that can be drawn from this. Naturally the method with the same assumptions as the generating process had the best performance.
It is important to note that both the performance of the machine learning algorithm (in terms of the error metric) and its runtime are very dependent on the source data in most cases.
I was impressed that random forests did so well for the irrelevant feature detection, given that they know nothing about gaussians. Though IIRC, you've used them to win Kaggle competitions, so maybe you already know their power.
The author of the blog post has promised more extensive tests with other datasets in future posts. Also there is an ongoing GSoC project for setting up a systematic benchmark infrastructure + performance optimizations for the scikit-learn project. So let's wait and see. We will soon have more meat for finer analysis.
One unmentioned caveat of SGD is how to configure the learning rate schedule. scikit-learn is using Bottou's tricks that seem to work reasonably well in practice but it might even be better to implement the online estimate of optimal learning rate schedule from this NIPS 2012 pre-print: http://arxiv.org/abs/1206.1106 (No More Pesky Learning Rates).
I think that in this case the data was generated in a uniform manner (centered and with isotropic variance). So it might not greatly impact the performance. ~50% training error is about the best you can get in a completely non-linearly separable dataset.