IMHO, creature types should not give blanket immunities. Magic is MAGICAL, it should be possible to charm a skeleton or energy drain a construct. All creatures should be subject to critical hits, stunning, etc - a talented rogue can Sneak Attack an ooze right in its nucleus, a monk can knock out even a golem.
Constructs and undead should have Constitution scores (equal to 10 + their CR if converting from the 3.5 MM). They are immune to ability damage/ability drain/disease/fatigue/nonlethal damage/poison from nonmagical sources, but susceptible to those effects from magical sources.
Even mindless creatures should have Intelligence scores (1-2 for oozes and vermin, 3+ for constructs and undead that can understand orders - if a brutish elemental gets an Int score they should too). They are susceptible to mind-influencing effects.
The chassis of each type should be improved, in line with the principles of the LA-Reassignment Thread. Racial Hit Dice should be functional - no more fey with 1/2 BAB, or creatures with only 2 skill points per HD and all poor saves.
Revamped Creature Types
Beasts (or perhaps "Creatures" or "Monsters")
Non-humanoid creatures, generally relying on physical might, racial Hit Dice, and natural weapons.
Hit Die: d10
Skill Points per level: 4
Saves: Good Fort & Ref, poor Will
Special: Low-light vision, ignore penalties to Intelligence score when calculating skill points (due to natural instincts).
Animals, dragons, magical beasts, oozes, plants, vermin
Some aberrations (e.g. aboleths)
Some constructs (e.g. animated objects)
Some corporeal undead (e.g. nightcrawlers)
Humanoid or part-humanoid creatures, generally relying on skill, manufactured weapons, class levels, and magic.
Hit Die: d8
Skill Points per level: 6
Saves: Good Ref & Will, poor Fort
Special: Can replace 1st Hit Dice with a class level.
Giants, humanoids, monstrous humanoids
Some aberrations (e.g. illithids)
Some constructs (e.g. iron golems)
Most corporeal undead (e.g. ghouls)
Divine creatures of pure magic, whose body and soul form one unit. They never grow old or die of old age (though they can be slain).
Hit Die: d12
Skill Points per level: 8
Saves: Good Fort, Ref & Will
Special: Darkvision, detect chaos/evil/good/law/magic at will, Low-Light Vision.
Elementals, fey, outsiders
Some aberrations (e.g. naga)
Some constructs (e.g. inevitables)
Some magical beasts (e.g. sphinxes, unicorns)
Some monstrous humanoids (e.g. hags)
Some undead (i.e. incorporeal undead)
Revamped Creature Subtypes
Alignment Subtypes ([Chaos], [Evil], [Good], and [Lawful])
Apply as they did originally, save that all Immortals gain the alignment subtypes matching their alignment (only true neutral Immortals do not gain these subtypes). An Immortal cannot change their alignment (and therefore their alignment subtypes) without receiving an atonement spell or similar effect. Certain powerful effects can grant these subtypes to non-Immortals (e.g. an aura of corruption around a cursed tomb could grant the [Evil] subtype to local Beasts). A creature's natural & manufactured weapons gain the alignment matching their subtypes.
Applies to a Beast (e.g. an animated object), Mortal (e.g. an iron golem), or Immortal (e.g. an inevitable) that originally had the construct type. [Construct] creatures always have good Fortitude saves, are immune to nonmagical ability damage/ability drain/disease/fatigue/nonlethal damage/poison and do not age, breathe, eat, or sleep. They heal naturally (due to the magic imbuing them).
Applies to a Beast or Mortal that was originally an aberration, dragon, giant, magical beast, monstrous humanoid, ooze, plant, undead, or vermin. All Beasts other than mundane animals are [Monstrous] (even dire animals), all Mortals other than humanoids are [Monstrous]. All [Monstrous] creatures gain darkvision.
Applies to [Monstrous] Beasts that were originally dragons. [Dragon] creatures have d12 Hit Dice.
Applies to Immortals that were originally elementals as well as some outsiders (djinn, tojanda, etc.). [Elemental] creatures have one or more of Air/Earth/Fire/Water Mastery, and always have at least 1 elemental subtype (see below).
Elemental Subtypes ([Acid], [Air], [Cold], [Darkness], [Earth], [Electricity], [Fire], [Light], [Sonic], [Water])
Not to be confused with the [Elemental] subtype itself, grant immunity to a particular energy type or effect (e.g. spells with the [Light] descriptor and similar effects) and often certain other abilities (e.g. the [Fire] subtype often grants the Burn special attack, the [Water] subtype grants a swim speed, etc.). Certain non-[Elemental], non-Immortal creatures can have elemental subtypes (e.g. oozes with the [Acid] subtype, dragons with the [Fire] or [Water] subtypes, etc).
Applies to Immortals that were originally fey. Almost all [Fey] creatures also have the [Native] subtype.
Applies to [Monstrous] Beasts and [Monstrous] Mortals that were originally giants or monstrous vermin. [Giant] creatures always have good Fortitude saves.
Applies to [Monstrous] Beasts that were originally oozes. Oozes have blindsight and are amorphous (they have all-around vision and gain Improved Uncanny Dodge).
Applies to [Monstrous] Beasts that were originally plants.
Applies to [Monstrous] Beasts (e.g. nightcrawlers), [Monstrous] Mortals (e.g. ghouls), and Immortals (e.g. ghosts and other incorporeal undead) that were originally undead. Functionally identical to the [Construct] subtype, save for interactions with effects that specifically affect undead (e.g. negative energy, turn undead, etc). Templated undead (e.g. skeletons, zombies, etc) are [Monstrous] Beasts or [Monstrous] Mortals, as appropriate.
Extraplanar, Incorporeal, Native, Shapechanger, Swarm
"Shelved" Subtypes (Angel, Aquatic, Archon, Augmented, Goblinoid)
These subtypes apply only in very limited circumstances or individual monster entries, and are often common sense (goblins are goblinoids, kobolds are scaly reptilians, etc). Not necessarily deleted, but refer to them only as necessary.