I average in the mid 30s, and have several cubes. I bought some of the garden variety rubik's cubes found in bookstores, and although they are hit and miss, some of them will turn out to be fantastic.

However, I second the DavidPFarrell's recommendation to check out PuzzleProz. I bought my cube lube from them, and their DIY kits look solid and reasonably priced. A nicer cube doesn't substitute for weeks of practice and memorization, but it can certainly help

Starcraft has been out for TEN years and it also just received a similar patch. Although a nice gesture on Blizzard's part, I've been working with disc images of Blizzard games for a while now (on a XP setup no less)