I've played a few half-celestials; IMO, +3 ECL is fine. At low levels, the loss of just 3 class levels can be close to crippling; at high levels, the half-celestial should be about on par with all of the characters that are 3 levels ahead.
The ECL has the most effect on spell-casters, and on classes that are heavily level dependant, like monks. Classes like fighter and rogue don't suffer much at all (except in terms of base attack bonus -- a half-celestial fighter has to wait 'till he's effectively 11th level to take Improved Crit), and half-celestials make for very good paladins.
If you're really worried about the half-celestial out-shining the other characters, set the ECL to +4. Being out 4 hit dice, 4 skill ranks, 2 full spell levels, at least one feat, and of higher-level abilities in general should more than compensate for the 1/2-celestial abilities.
Keep in mind that the ECL level for half-celestial doesn'tcount towards the spell-like power progression -- a half-celestial with Resurrection 1/day is a 22nd level character, not a 19th.