The concern about time just reminded me that pigz exists. It even has --rsyncable!
(pigz produces output that’s compatible with gzip, using multiple cores to do the compression and resulting in much shorter wall clock time vs ordinary gzip.)
It’d probably be a good idea to run it niced into oblivion, since its many threads could have a much bigger impact on a running instance’s peformance than gzip’s one thread.
Might be worth checking out, especially for that large instance. 
Edit:
I did some quick tests on my not-so-huge backup.
At the default compression level, pigz --rsyncable output is very slightly bigger than gzip --rsyncable output. It deduplicates just as well.
The size cost of pigz --rsyncable is a ~0.736% gain versus plain gzip for my data. (For comparison, gzip --rsyncable is a ~0.281% gain.)
The wall clock time improvement is impressively linear. With 4 real cores on my laptop, pigz --rsyncable takes ~0.568 seconds (wall clock time), compared to ~2.222 seconds for plain gzip.
There may be a sweet spot where you can “have your cake and eat it too” with shorter wall clock time and smaller but dedup-friendly output, by combining a switch to pigz (+ --rsyncable) with a bump in the compression level.