I've been playing around some with raw transactions; one of them had a size of 4401 bytes when signed. So for a test, I compressed it with bzip2, and the resulting (hex) was only 1680 bytes
cat signed.txt | bzip2 | openssl enc -base64 -A -out signedbz2.txt
That's almost a third of space that's saved, so the fee would go down noticeable too, and more transactions would fit into a block.
I know keys can be compressed, but what about a transaction itself?