Must enable_shared_from_this be the first base class?

When ~A() and ~B() run, can I be sure that the storage where C lived is still present?

No, and the order of the base classes is irrelevant. Even the use (or not) of enable_shared_from_this is irrelevnt.

When a C object is destroyed (however that happens), ~C() will be called before both ~A() and ~B(), as that is the way that base destructors work. If you try to "reconstruct" the C object in either base destructor and access fields in it, those fields will have already been destroyed, so you will get undefined behavior.