At 16 pixels wide, a character is mostly a silhouette with a colour.
One strong shape
Give each character one thing nobody else has: a hat, a hood, a staff. Then check it in solid black.
Outline with colour
A coloured outline that picks up the fill next to it looks softer than black and reads just as well.



