1) I'd add a volume column to the cart
2) You can determine small medium or large based on volume so they shouldn't have to assign that separately
3) You could have logic that uses two delivery methods in this case if that is what the customer would do
4) I'm not sure about that, maybe ask the client
5) I would use the zones since you can store that in the database and easily filter for it on the checkout page... I imagine it is significant.
6) Maybe compare the three and use the cheapest option
8) You would break up the cart into packages and then could evaluate each package and cross check the delivery companies for each package to find the best rate.