Humanoid phoenixes! Current LA is +5: I dare you to find anything with more than +2 original LA where WotC's value didn't get changed.
Phoelarches have seven monstrous humanoid RHD, which is not great but not terrible either. Their stats, most notably dexterity and charisma, gain bonuses ranging from +0 to +6. Unsurprisingly, they have the [Fire] subtype, which is never bad. +2 natural armor is not very notable, Great Fortitude and Alertness are bonus feats: aka the stuff too bad to ever pick yourself, but good enough to notice.
Special qualities are as follows: immunity to disease and poison (nice), 1d6 Heat (not bad), the ability to heal from fire damage (free out-of-combat healing), and two abilities that are only relevant when the Phoelarch dies. Death Throes, aka 'If I go down I am taking half the party with me' is nothing surprising, but Rise From The Ashes is more interesting. It causes a mysterious egg to remain when the phoelarch dies, which after 24 hours hatches into a new, majestic bird-creature. Not relevant for a PC, but cool to mention.
Spell-likes are at-will Light and Scorching Ray, 3/day Produce Flame, and 1/day Fire Shield. It's neat enough, if a bit one-sided.
So what LA fits here? I'm not going to pretend that playing a phoelarch dooms your character to uselessness, and 8d6 consistent fire damage that can be augmented with sneak attack is hardly bad. The free out-of-combat healing has its utility as well, and fire immunity is useful against a number of things. Finally, the stat boosts are reasonably good all-around.
In my opinion, a phoelarch would definitely be a +0 if the target is tier 4. It doesn't stack up to tier 3 characters of the same level, though, and would be -0 LA in those cases.
Aka the magic birbs phoelarchs turn into after death. 3 magical beast RHD, Heat-augmented bite and claw natural attacks that set foes ablaze, a reasonable fly speed, an okay breath weapon that can be augmented with feats, pretty good stats (apart from intelligence), Alertness, and Healing Fire. Phoera also get Rise From The Ashes, which creates new Phoera.
However, being dumb as bricks and thumbless doesn't make up for those abilities. -0 LA, though again not entirely unplayable.
Vazalkyon and Vazalka
Very poorly-written cold-based variants. To illustrate what I meant by 'poorly written', by RAW, vazalkyons still have fire SLAs and a Vazalka's Rise From The Ashes leaves a phoera egg.
That said, the changes are minimal enough that I think the same LAs should work fine.