The planktivore Anthias you usually think of need at least 3 to 4 feedings a day, better more.
These guys just don't have a large enough stomach to eat enough during one feeding.
There are other Anthias species that are more like groupers and who can eat a lot at once. Odontanthias borbonius would be one (but they may eat small shrimp as well once grown to full size).
My experience with marine bettas (and I had quite a few of them) is that they are at some point likely to eat even cleaner shrimp - especially if you let them go hungry for a few days. The shrimp that may be safe are those large or scary enough like Stenopus hispidus, but even with those I wouldn't give you a guarantee.
My regal angels are not really zoa killers: one is nibbling on the large green paley's tentacles but leaves the smaller ones alone. Another is in a tank with several zoa colonies and doesn't even look at them.
In general I feel they usually only nibble on zoas as a form of self medication if they feel sick but not necessarily take them for food.
I don't see what the problem with a flame angel would be. I had a pair once and they were no trouble at all. Though I would always advise against keeping single dwarf angels - those have too much time on their hands. They either become jerks or mentally disturbed. These are fish that need social interaction with members of their own species to behave normal.
In the end, flasher or fairy wrasses may be your safest bet.