For example:
Advanced Half-Celestial Dire Lion
Huge Outsider
Hit Dice: 19d8+136 (221 hp)
Initiative: +3
Speed: 40 ft. (8 squares), fly 80 ft.
Armor Class: 23 (-2 size, +3 Dex, +12 natural armor), touch 11, flat-footed 20
Base Attack/Grapple: +14/+36
Attack: Claw +27 melee (1d8+14)
Full Attack: 2 Claws +27 melee (1d8+14) and Bite +21 melee (2d6+7)
Space/Reach: 15 ft./10 ft.
Special Attacks: Improved Grab, Pounce, Rake 1d8+7, Smite Evil 1/day, Spell-Like Abilities (Protection from Evil 3/day, Bless 1/day, Aid 1/day, Detect Evil 1/day, Cure Serious Wounds 1/day, Neutralize Poison 1/day, Holy Smite 1/day, Remove Disease 1/day, Dispel Evil 1/day, Holy Word 1/day, Holy Aura 3/day, Hallow 1/day, Mass Charm Monster 1/day, Summon Monster IX (celestials only) 1/day, Resurrection 1/day; Caster Level 19th; DC is Charisma based)
Special Qualities: Darkvision 60 ft., Low-Light Vision, Scent, Empathic Link, Improved Evasion, Share Spells, Share Saving Throws, Daylight at will, Immunity to Disease, Resistance to Acid 10, Cold 10, and Electricity 10, Damage Reduction 10/magic, Spell Resistance 35
Saves: Fort +19 (+4 vs poison), Ref +14, Will +9
Abilities: Str 38, Dex 16, Con 26, Int 6, Wis 16, Cha 14
Skills: Hide +21(22), Jump +29(11), Listen +27(22), Move Silently +29(22), Spot +27(22), Survival +14(11)
Feats: Alertness, Run, Weapon Focus (Claw), Power Attack, Improved Bull Rush, Awesome Blow, Snatch
Alignment: Lawful Good
Challenge Rating: 15 (8 (base) + 3 (half-celestial) + 3 (+9 HD advancement) +1 (size increase))
Note, this is actually one CR too high (you could at most have a CR 14 creature with a fly speed at 18th level according to the DMG; forgot the size increase CR change at first
), but it's probably good enough as an example of what is quite possible, and if the DM is lenient enough, he or she could allow it to you at 18th level already).
Bye
Thanee