I think you've ruled out the two service providers as the cause, and your phone should work extremely well on a FiOS-based network.
However, you didn't specify where the sound quality problem occurs. Does the other party on the call sound bad to you, or do you sound bad to them, or both? Which audio device are you using -- the phone's handset, the phone's speakerphone, a USB-attached headset, a RJ-9 attached headset or a Bluetooth headset?