Don't forget that IBM actually designed Lucifer which was 128bits but it was the (edit:s/NSA/NHIS) that truncated it to 56bits and named it DES. So maybe this is an example of "6 of one or half a dozen of the other"?
And don't forget that Eli Biham smote Lucifer with differential cryptanalysis, found more than half of the keys insecure, reduced its security to 235, and published a journal article concluding that NSA strengthened the cipher design; DES was better than Lucifer.
Maybe 3 decades after it was released according to this paper; http://scholar.google.ca/scholar_url?hl=en&q=http://59.1...
Even if the NSA appointed S-Boxes did improve Lucifer then decreasing the block size does not really improve on your point.
