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.