Another vote for a chest freezer. We had a large and comparatively energy-efficient upright for 15 years, but a remodeling project took its space, and new space opened up that a chest freezer used more efficiently. We noticed a big difference in our electric bills (around 20%) the first year, and the second year we had it, we had a 9-day power outage in the Great Ice Storm of 98; the chest freezer's contents stayed frozen, even when opening it every few days to transfer food to a cooler for immediate needs. The upright, in a two-day outage in the 1980s, half-thawed its entire contents.
The big downside of a chest freezer is enforced organization. If you're the sort of person who tosses everything into the back of the closet and then gets upset because you can't find anything, you don't want a chest freezer. But if you're willing to enforce a rigid order--in ours, we have four sliding baskets that came as original equipment which we use for miscellaneous catch-alls: leftovers, bits-bags for stock, and other difficult-to-categorizables; below that, everything is in stacking plastic bread-truck boxes of similar products: all the broccoli and other coles here; all the peas and beans there; all the lamb in those two; last year's deer in that one; the fish in the other one; miscellaneous birds in this one here. When boxes are emptied, they're refilled with gallon water jugs to retain the cold in case of power failure (and because a full freezer runs more efficiently than a half-empty one). For no other reason that it made sense at the time, all the meat lives to the right, and all the vegetation lives to the left.
Before we found the bread boxes, we used plastic grocery bags to pigeon-hole things. Now that grocery bags are becoming scarcer, cloth bags, as a poster mentioned above, would be a far more durable alternative.
