(Psi)SeveredHead
Adventurer
Martian Invader: CR 9; Large aberration (extraterrestrial); HD 8d8+11; hp 47; Mas 13; Init +2; Spd 20 ft.; Defense 21, touch 11, flat-footed 19 (–1 size, +2 Dex, +10 natural); BAB +6; Grap +15; Atk +11 melee (1d4+6, tentacle); Full Atk +11 melee (1d4+6, 8 tentacles) and +5 melee (1d8+3, bite); FS 10 ft. by 10 ft.; Reach 20 ft.; SA Improved grab, constrict; SQ Low-light vision, fast healing 5; AL Martians; SV Fort +3, Ref +4, Will +7; AP 0; Rep +0; Str 22, Dex 15, Con 13, Int 10, Wis 12, Cha 3.
Skills: Hide +6, Knowledge (technology) +3, Spot +12.
Feats: Alertness, Planetary Adaptation (high-G), Toughness.
Advancement: By character class.
Woah! That's quite powerful. IMO, it needs two changes, however.
1) Mars has low gravity, so you need to change that feat.
2) If you give it fewer Hit Dice (but make the average Martial Invader still have 8 Hit Dice) that gives it more class flexibility and more skill points, too! For instance, this guy can't pilot a mecha! He needs two more feats for that. (You can just make those free, of course.)
But picture this guy with 5 levels of Mecha Jockey instead of 5 (relatively weaker) Hit Dice!