Can the Arduino run a "boot" routine when power is applied?
Yes, it does.
I want the box to immediately startup and check the date after a battery is connected.
It won't be immediate, but it will be pretty quick.
Can it check somehow for whether the clock module has power
Not without modifications to the clock module (connect the battery leads to an analog pin and ground).
and execute some action if it doesn't?
What would that action be? If the clock is dead, it no longer knows the time. The only appropriate action that I can think of is to open the box.
I'd like to the final product to be as small as possible. Can I develop on something like the Uno, then swap that out for a Mini when I'm ready to finish the box?
Yes.
Will there be any issues with the Mini driving a servo?
Driving a servo, no. Powering the servo, yes. Don't do that.