Ogres: now with magic.
Ogre mages are a lot like their mundane cousins in terms of chassis. Their strength scores are equal, they only have one more HD, and their natural armor and speed are equal as well. However, ogre mages also have a fly speed (supernatural, but with good maneuverability), and their non-strength ability scores are universally higher (sometimes by as much as ten points). Their skill list is also somewhat better, though that's not saying much.
Ogre mages also can Change Shape into any humanoid or giant from Small to Large size. It's especially fun when combined with the old Return To Nature trick: be Large during combat and Fine when stealth is required.
They also have Regeneration that's overcome only by acid and fire. That's pretty relevant regardless of level.
Finally, ogre mages get a few SLAs. Sleep is utterly horrible (this is a CR 8 monster, guys, what were you thinking?), Cone of Cold is probably not worth it except against giant groups, and Charm Person has been on the table for a while now, but Gaseous Form is a decent panic button or buff, especially since its one of its main downsides doesn't apply to ogre mages. Darkness and Invisibility (not self-only!) at-will are also quite useful if applied well.
Then again, giant RHD are still sucky, and a too-high LA would turn the ogre mage into a second-rate buffer rather than a truly useful combatant. I'm going to go with +2 for now.
Next are a bunch of iconic monsters: oozes!