<p>We recently switched some of our sites from deflate to gzip and noticed a significant increase in cpu load on our servers.</p>

gzip is, basically, deflate with some additional headers. So there should not be a significant performance hit. Now, maybe your deflate tool is just more efficient than your gzip tool. Are you using the same tool for both compressions or two different ones?