There are plenty of CDNs out there that can gzip and set proper expire headers. However, if you're talking about something similarly priced, you likely won't find anything. The only CDN I know of similarly priced (Highwinds) has substantial issues with "small" files --- they are targeted toward larger media files.
Well.. rackspace and amazon (the first ones I asked do not gzip). Edgecast offers that service but it is extremely expensive, they request very long commitment, I did not like how they sell (looks like they are afraid to tell you the price, with those prices it's understandable...) and they even lied me saying that only simplecdn and amazon (the ones I mentioned in the chat) offer pay-as-you-go option. I just asked also softlayer (they also offer pay-as-you-go option by the way) and they do exactly what we want and they have really good prices if you pay in a monthly term instead of pay as you go.
I am not looking anymore for a new CDN, softlayer is the one chosen.
Since we are having problems with simplecdn during traffic surges and also some other problems time to time, probably this could be an interesting solution: DNS round robin of static.mydomain.com with simplecdn (added several times also with mirror buckets) and cloudlayer(softlayer). This way there will be traffic to softlayer but more to simplecdn but if simplecdn fails, the requests will go to softlayer.