If your configuration is local LAN only then normally you won't have any issues with voice quality.
Having said that, I can recall the same issue with a customer of me, and my customer who had around 40 switches (mostly 3750) and suddenly had choppy voice. Finally it turned out that one switch was defect and caused somehow intermitted huge ammount of traffic causing voice packets to get lost.
In our own office I managed to bring down our own voice network with Norton Ghost using multicast, even phones got unregistered.
So really check the network, if possible close all PC's and servers, so the switches only have data in Voice VLAN, also check if STP has been running many times without reason, this could point to bad cabling.
Low volume on PSTN calls could be solved by tweaking Input Gain and/or Output Attenuation. Be carfull with this, read first information on the Cisco web site. I have never tried this myself.
Regarding the low volume, you are making PSTN calls directly out the voice gateway and not going through a PBX, are you?
For the choppy, hit the ? key twice on the IP Phone, see what the jitter, max jitter and lost packets are on a choppy call. These statistics will represent the IP packet statics between that IP phone and the voice gateway.
I prefer not to use autoqos, since you might not get the optimal setting you are expecting.
if you ip/wan is working fine, then you may have a issue with bandwidth your providing. there needs to be some more info here. check codec requirement, db level and autoqos setting for PSTN interface controller whether E-1, T-1 of ISDN
hope i could be of some assistance