All this debate around the djinn is making me efreet of judging this thing! I'll show myself out.
10 outsider RHD: not a bad start. Improved Initiative as a bonus feat (looking back, djinn have it too). Good stats all around: intelligence and dexterity are inferior to the djinn's but strength is much higher. Large size with reach, as well as two natural slam attacks that'll probably never get used. The Fire subtype is a marginal increase in power, telepathy has already been discussed, and the fly speed is good (if a little slow).
More interesting: the efreeti's supernatural powers. Heat is a little ambiguous whether its damage applies to weapon attacks: if it does, that's great, if it doesn't a weapon is still better.
Change Size is mostly useful for use on self. Any character that can benefit from Enlarge Person will probably have gotten a ring or permanent spell by now, but any melee character benefits from becoming Huge twice per day. Of course, it's also useful as a debuff, but the low save DC and limited targets discourage that.
Plane Shift has been discussed to death. My opinion remains that it's useful, but not game-breaking.
Change Shape is okay. Amongst all those humanoids and giants, there's bound to be one or two interesting forms, and it'll stop angry mobs from lynching you. Disguise is technically an efreet class skill; put points in it!
Finally, the SLA's. The at-wills (Detect Magic, Produce Flame, Pyrotechnics and a sole Scorching Ray) are pretty meh, and the same goes for 3/day Invisibility. Wall of Fire is more interesting, but nothing great. Gaseous Form (1/day) isn't too impressive.
After all these lackluster SLA's, suddenly there's two quite good ones. Permanent Image (1/day) is permanent (duh) and creates an incredibly convincing illusion. What's more; it's SLA-ness removes the usual 100 gp cost.
Finally, Wish, which we've all talked much about. The Efreeti gets it thrice per day, to nongenies only. Guess why it got the asterisk?
Compared to the noble djinni, the efreeti has superior melee ability, worse speed, worse SLA's, and about equal special abilities. For now, I'll assign them +1*, which should balance things out.