I took a copy of MaxMind's free city-level geocoding database a year or so ago, and the file size was roughly 30MB.
Checking their site again today (July 2012), the equivalent file is now only 17MB, approximately half the size.
I cannot find any reference to this online. Does anyone know if they've reduced the quality or range of their free offering, or whether it's just an improvement in the binary encoding/layout of the data that resulted in the smaller file.