If they aren't enthused about more celestials, maybe more templates would work.
Angel-touched:
The angel-touched creature grows feathery wings. If a creature has non-feathery wings, they become feathery. If the creature already has feathery wings, it gets an extra set (doesn't change speed). All angel-touched creatures have a fly speed of X unless they already had a faster fly speed.
The creature's type changes to celestial. Angel touched creatures have a natural inclination towards LG alignment, but DM's can chose not to change the creature's alignment. It gains immunity to radiant damage, and does 1d8 extra radiant damage on melee or breath weapon attacks....
Paragraph about in general, angel touched adds 2 to the CR of creatures in CR range...1 to the CR of creatures in CR range.... and does not change the CR for creatures above CR Y, but DM's are encouraged to check with the section on monster creation in the DMG if they have concerns.
So if you can't have new celestials, you can mess with the murderhobos by dropping angel-touched red dragons on them.