The headset will work fine with the 3GS, although the dock will not fit. You can use the travel dock to pair, then use it alone to charge the headset.
I'm using this setup with my 3GS. The 3GS sits in a 3G dock, and I keep the travel dock stuck under the edge of my table for the headset (it hides the cable). I do need two USB chargers, though. I have the Belkin 3 outlet / USB charger adapter, which has 2 ports. It saves an outlet (and a USB charger).
btw: the audio quality is improved on the 3GS. I think it's an overall Bluetooth improvement, though, and not something specific to the Apple headset (the audio in my car's integrated Bluetooth "uConnect" system has also noticeably improved).