If you prefer to use your System with the OpenSource Radeon Driver, Starcraft 2 is flawlessly playable at lowest graphic settings!
It works for me on:
Fedora 15
Kernel 2.6.38.8-35.fc15.i686.PAE
Intel(R) Core(TM)2 Quad CPU Q9300 @ 2.50GHz
4GB RAM
Radeon HD 4870 1GB VRAM
OpenGL vendor string: X.Org
OpenGL renderer string: Gallium 0.4 on AMD RV770
OpenGL version string: 2.1 Mesa 7.11-rc1
OpenGL shading language version string: 1.20
OpenGL extensions:
No extra tweaks applied (except using OpenGL...), no default packages replaced!
All you have to do is installing the s3tc from the Fedora repositories!
Update 3.4.2012:
On Fedora 16 the situation has even improved! (Texture Quality from low to middle)
Stay tuned....
If you find any tweaks to increase performance, PLEASE let us know;)