rbrockman, let's step back up to the 30,000 ft level, as they say.
A device with an embedded Arduino is shipped with working software.
When it is time to upgrade software, would you be willing to ship a replacement device, pre-programmed with the new software, in exchange for the original, returned to you? You seemed willing to ship an SD card with pre-loaded software in your original scenario.
Since you could reprogram the devices you received back, and ship them to other customers, the cost to you would be a set of "in transit" devices, some of which you might not get back. Compare that risk to the expense of buying SD cards, none of which you expect to get back.
This seems to be the easiest, most foolproof, and least troublesome for the customer, but I suppose it depends on the size and cost of the "device," and whether it is embedded in something else or stand-alone.
Just trying to brainstorm for you...