Hi tbharber,
On the 11" MBA with 2GB of RAM I'm getting about 12-14 FPS on medium settings (on average), based on the on-screen unit count. It would peak at about 25-26 FPS then would dip several times to <10 FPS when I filled the screen with roaches and marines. If I dropped the settings to low and turned everything to low I saw my average FPS move closer to 20-21 FPS and peak at about 28-29 FPS. Again though, when things got busy it would quickly dip to 10-12 FPS. I suspect that the 4GB of RAM upgrade would help, but I certainly wouldn't expect 15-20% gains as a result of the extra RAM.
On the 13" MBA with 2GB of RAM I'm getting about 22-24 FPS on medium settings (on average), based on the on-screen unit count. It would peak at about 32 FPS then would dip several times to <15 FPS when I filled with the screen with carriers and void rays. If I dropped the settings to low and turned everything to low I saw a similar FPS jump and was setting close to 30 FPS with the occasional jump to the high 30s. I never was able to routinely stay over 35 FPS under any scenario. Again, I suspect doubling the RAM would help.