Z-something in The Robots of Death was black, if I recall...(though it's years since I saw that one) as was the Matrona in The Trial of a Time Lord. And they both have lines. I agree about the Movellan lady, though same caveat as for The Robots of Death, there.

Oh, what about Ping-Cho? She'd have to take the biscuit, I'd think.