i recommend you turn it down to x8 as this will have a similar perfomance to x4msaa having it on x16 will be the equivilant perfomance hit of x8msaa which will cripple any systems fps.
also if your screen is nativley bigger than 800/600. go into the windows control panel and there should be some screen options that enable boredring on smaller screen sizes. disable it and the screen should then auto upscale the smaller rez to fill the whole screen without any real performance hit other than video ram usage.
you should then be able to forgo any AA settings and get the most fps you can.. along with better shadows and textures.