Perhaps you should have a look at pigz, a multi-threaded implementation of gzip. It uses the same flags as gzip, so -# specifies speed (-1 runs the fastest with the least compression ... -9 runs the slowest with the best compression), and by default it spawns as many processes as you have processors. I've never done any formal benchmarks, so I'm not qualified to speak as to its efficiency, however.
Based on your late-90's upload rate (and assuming you're working with large files that compress nicely), I'd say the more time you spend on compression, the less overall time you're looking at. That 100kb/s (theoretical) limit is really the first bottleneck you should be fixing, though.
[edit]: I completely misread that as kilobits/s. Point still stands minus the 90's bit.