1. Games began at or near max FPS (30+)
2. After a while, the game will stutter down to wretched FPS (5, etc)
3. Turning the graphics from ultra to low doesn't make a difference
Number 3 is the biggest thing here. If you notice that changing all your graphics from ultra down to low makes no impact on the game's performance, something is up. What I tried at first was "stressing" the GPU/CPU into taking larger loads. I'd begin a custom game with 8 people and turn up all settings to ultra. Then I'd open another game and it'd be smooth all through.
The solution is that some nvidia cards (and perhaps amd, but I'm using an nvidia laptop) uses a "power-saving" mode. I've even heard of people who have super good computers with amazing GPUs have this problem because their card goes into its special, low-clock power save mode and doesn't recognize that SC2 requires a lot more speed to get it going. Here is how to fix the problem (first you should get the latest drivers so we're looking at the same panel):
1. Right click on desktop
2. Open nvidia control panel
3. Under 3D Settings on the left panel, select "Manage 3D Settings"
4. Scroll to "Power Management Mode" and, to its right, change the selection to "Prefer Maximum Performance"
I don't know if this will work for you but it worked for me and I haven't seen this fix on the forums or online so here it is =D