Genie, Qorrashi (CR 6)

Large Outsider (Cold, Extraplanar, and Lawful)
Alignment: Always lawful neutral
Initiative: +7 (+3 Dex, +4 Improved Initiative); Senses: darkvision 60 ft., Listen +12, and Spot +12
Languages: Telepathy 100 ft.

AC: 18 (-1 size, +3 Dex, +6 natural), touch 12, flat-footed 15
Hit Dice: 7d8+21 (52 hp)
Fort +8, Ref +8, Will +7
Speed: 30 ft., fly 60 ft. (perfect)
Space: 10 ft./10 ft.
Base Attack +7; Grapple +16
Attack: Slam +11 melee
Full Attack: 2 slams +11 melee
Damage: Slam 1d8+5 plus 1d6 cold
Special Attacks/Actions: Chill, frostbite, spell-like abilities
Abilities: Str 20, Dex 17, Con 16, Int 14, Wis 15, Cha 15
Special Qualities: icewalking, immunity to cold, outsider traits, plane shift, vulnerability to fire
Feats: Combat Reflexes; Dodge; Improved Initiative
Skills: Bluff +12, Concentration +13, Diplomacy +16, Disguise +2 (+4 acting), Escape Artist +13, Intimidate +14, Listen +12, Move Silently +12, Sense Motive +12, Spellcraft +12, Spot +12, and Use Rope +3 (+5 with bindings)
Advancement: 8-14 HD (Large); 15-21 HD (Huge)
Climate/Terrain: Elemental Plane of Air
Organization: Solitary, pair, company (3-4), or band (6-15)
Treasure/Possessions: Standard

Source: Frostburn

Chill (Ex): In addition to its normal slam damage, a qorrashi deals an extra 1d6 points of cold damage with a successful melee attack.

Frostbite (Ex): A creature that sustains any cold damage from a qorrashi's melee attacks must make a DC 16 Fortitude save or become frostbitten. Creatures suffering from frostbite are fatigued (cannot run or charge; -2 penalty to Strength and Dexterity). These penalties end when the cold damage is healed by any means. The save DC is Constitution-based.

Spell-Like Abilities: At will - endure elements, invisibility (self only); 3/day - cone of cold (DC 17), ice storm; 1/day - create food and water, gaseous form (up to 1 hour), major creation (created vegetable matter is permanent), persistent image (DC 17), wind walk. Caster level 14th.

Icewalking (Ex): This ability works like the spider climb spell but applies to all icy surfaces. A qorrashi can move normally on any icy surface.

Outsider Traits: A qorrashi cannot be raised, reincarnated, or resurrected (though a limited wish, wish, miracle, or true resurrection spell can restore life). It has darkvision out to 60 feet.

Plane Shift (Sp): Like other genies, a qorrashi can enter any of the elemental planes, the Astral Plane, or the Material Plane. This ability transports the qorrashi and up to six other creatures, provided they all link hands with the genie. It is otherwise similar to the spell of the same name.

Telepathy (Su): A qorrashi can communicate telepathically with any creature within 100 feet that has a language.

Cold Subtype

A creature with the cold subtype has immunity to cold. It has vulnerability to fire, which means it takes half again as much (+50%) damage as normal from fire, regardless of whether a saving throw is allowed, or if the save is a success or failure.

Extraplanar Subtype

A subtype applied to any creature when it is on a plane other than its native plane. A creature that travels the planes can gain or lose this subtype as it goes from plane to plane. This book assumes that encounters with creatures take place on the Material Plane, and every creature whose native plane is not the Material Plane has the extraplanar subtype (but would not have when on its home plane). An extraplanar creatures usually has a home plane mentioned in its description. These home planes are taken from the Great Wheel cosmology of the D&D game (see Chapter 5 of the Dungeon Master's Guide). If your campaign uses a different cosmology, you will need to assign different home planes to extraplanar creatures.

Creatures not labeled as extraplanar are natives of the Material Plane, and they gain the extraplanar subtype if they leave the Material Plane. No creature has the extraplanar subtype when it is on a transitive plane; the transitive planes in the D&D cosmology are the Astral Plane, the Ethereal Plane, and the Plane of Shadow.

Lawful Subtype

A subtype usually applied only to outsiders native to the lawful-aligned Outer Planes. Most creatures that have this subtype also have lawful alignments; however, if their alignments change, they still retain the subtype. Any effect that depends on alignment affects a creature with this subtype as if the creature has a lawful alignment, no matter what its alignment actually is. The creature also suffers effects according to its actual alignment. A creature with the lawful subtype overcomes damage reduction as if its natural weapons and any weapons it wields were lawful-aligned (see Damage Reduction).