Ther are plenty of fish that would compliment what you have. Pseudochromis and basslets make excellent additions. Many colors to choose from. Just one per tank though. They are known to fight with their own kind unless tank raised.
I had a pajama cardinal by itelf for about three years. It was placed into another tank, but did just fine.
Blennies are another good addition. Many eat specific types of algae. Rock blennies (aka lawnmower blennies) are the most common algae eater in a marine aquarium. Not very colorful, but definitely full of personality.
You could try another perc. You'd need to get one that's bigger and no guaranttees it would work out. Mixing clown species in a small tank is a no no as you saw for yourself what can happen.
Keep in mind when dealing with clowns...they are just 'fancy' damsels. The attitudes are all the same lol. Even seen in the African cichlids you have. It is theoried that Afrian cichlids descended from damsels. Notice how they behave the same and 'talk' to each other the same and have the same terroristic attitudes. LOL
Thought you might like that last tid bit of info
We, as a people, know so much more about outer space than we do about our own oceans. This lack of knowledge can very well spell the dangers that lay in wait for us.
The oceans surely would swallow us before a rock comes down to smite the planet of it's life.