An appropriate creature with the template half-celestial (MM 144-6) gains a fly speed equal to twice its base land speed and good maneuverability. (As opposed to the average maneuverability granted by the templates half-dragon (MM 146-7) and half fiend (MM 147-9).) The Level Adjustment for a creature with the template half-celestial is +4.
Monster Manual Large creatures to which the half-celestial template can be applied with minimal fuss that then have a fly speed of at least 70 ft. include a blink dog (MM 28) advanced to at least 8 Hit Dice (minimum ECL 14), the centaur (MM 32) (ECL 10), an ethereal filcher (MM 104-5) advanced to at least 8 Hit Dice, an ethereal marauder (MM 105) advanced to at least 5 Hit Dice, an at least Large fire elemental (MM 98-99), a formian warrior (MM 109-10) advanced to at least 9 Hit Dice, a formian taskmaster (MM 109-10) advanced to at least 10 Hit Dice, the formian myrmarch (MM 110-1), the guardian naga (MM 192), a krenshar (MM 163) advanced to at least 5 Hit Dice (minimum ECL 11), the leonal (MM 142) advanced to at least 19 Hit Dice, the phase spider (MM 207-8), and the unicorn (MM 249-50) (ECL 12). Obviously, some of these make more sense than others. (A half-celestial centaur or unicorn? Sure. A half-celestial fire elemental or formian taskmaster? Not so much.)
Because their alignments aren't usually compatible, creatures that are atypical prospects for the template half-celestial include the achaieri (MM 9-10), the annis (MM 143), the dark naga (MM 191-2), the displacer beast (MM 66-7) (ECL 14), the frost giant (MM 122-3) (ECL 22), a hellhound (MM 152-3) advanced to at least 9 Hit Dice (minimum ECL 16), the howler (MM 154-5) (ECL 13), the lamia (MM 165) (ECL 17), a shadow mastiff (MM 222) advanced to at least 7 Hit Dice (minimum ECL 18), the spirit naga (MM 192-3), the winter wolf (MM 256) (ECL 13), a worg (MM 256-7) advanced to at least 7 Hit Dice (minimum ECL 12), and a xill (MM 259-60) advanced to 9 Hit Dice (minimum ECL 17). Again, some of these make more sense than others. Also remember that even if a creature is listed as always being a certain alignment that always doesn't actually mean always (see Alignment on MM 305 and this question).
What about half-celestial animals?
The core rules don't really support animals being the targets of the 5th-level Drd spell awaken [trans] (PH 202) first then somehow gaining the normally inherited template half-celestial afterward, but if the DM can be convinced this happens somehow or that awakened once-animal-now-outsiders naturally roam wild somehow or whatever, animals that after gaining the template half-celestial that have fly speeds of at least 70 ft. include the bison (MM 269-70), brown bear (MM 269), camel (MM 270), dire bear (MM 63), dire boar (MM 63), dire lion (MM 63), dire tiger (MM 65), dire weasel (MM 65) advanced to at least 7 Hit Dice, a dire wolf (MM 65-6), heavy horse (MM 273), heavy warhorse (MM 273-4), hyena (MM 274) advanced to at least 4 Hit Dice, light horse (MM 273), light war horse (MM 274), polar bear (MM 269), lion (MM 274-5), tiger (MM 281-2), and wolf (MM 283) advanced to at least 4 Hit Dice.
In all cases creatures without a listed ECL aren't given one here. The DM decides if a creature's ECL remains based on the creature's Hit Dice (like I've done here) when the creature's advanced to size Large; such a creature's Challenge Rating usually increase by an additional +1 when that happens (see Table 4–4: Improved Monster CR Increase on MM 294); what happens to its Level Adjustment is up to the DM.
Thus the most likely and conservative choices are the ECL 10 half-celestial centaur with fly 100 ft. (good) and the ECL 12 half-celestial unicorn with fly 120 ft. (good). Easily adjudicated but less likely to occur in nature are the ECL 13 half-celestial winter wolf with fly 100 ft. (good) and the ECL 17 half-celestial lamia with fly 120 ft. (good).
