DC power supply with DC input either polarity?
I'm wondering if a power supply can be constructed that accepts a DC
  input of either polarity.


It's called a bridge rectifier: -



The one above also has a smoothing capacitor and shows how the load resistor produces ripple.


  What would its size, cost and efficiency be?


Size can be a few tens of cubic millimetres to (normally) something like this: -



But, of course, for high power applications they can be bigger. Cost is a few pennies to many tens or hundreds of pounds/dollars and again, this depends on the power rating and operating frequency.

Efficiency - there is always a power loss due to the forward conduction losses of each diode. This will range from about 0.5V to over a volt depending on size/type of diode and current required by the load.


  Whenever I'm looking for exactly the right wall wart in a box full of
  them I wish everything just accepted 100-240VAC.


Most modern ones do accept a wide range but older designs just produced a DC output voltage proportional to the AC input voltage. Modern ones use switching converters to regulate the output voltage.