To me, "Invincible, so long as his feet remained firmly planted on his native soil" (Alcyoneus) sounds a lot like this:
Instantaneous Healing (Ex): If he begins his turn in contact with the earth, Antaeus instantly regains all lost hit points. This works just like natural healing. It does not restore hit points lost from starvation, thirst, or suffocation, and it does not allow Antaeus to regrow or reattach lost body parts.
Born with Armaments (give 'em special armor and/or weapons) could be magic weapons/armor with a specified enhancement value (+3 for Large, +4 Huge, +5 Gargantuan, +6 Colossal?). Not sure, but that would leave the DM with some freedom.