Let me first show why your intuition goes wrong. For this, consider a slight variation of the game: Again, Andy, Bruce and Charles draw a ball in turn, but this time with putting the ball back. The first one who draws the red ball wins. If neither draws the red ball, nobody wins.
Now who has the best chances at this game? Well, obviously Andy: If he draws a red ball, he already has won, while Bruce can only win if he draws a red ball after Andy drew a white ball, and Charles can only win if both Andy and Bruce drew a white ball, and he then drew a red one.
Now, how to fix this first-mover advantage? Well, obviously we have to increase the probability of the others to win to make up for it. One obvious way to do so is if there are less white balls in the box for the later players. So just remove a white ball after each draw.
However, if Andy draws the red ball, he has won anyway, so it doesn't matter whether and what we remove afterwards, so we can instead just say Andy keeps the ball he has drawn. If the ball was white, it improves the chances of Bruce, and if it was red, it doesn't matter anyway. For the same reason, Bruce can just keep his ball, and of course for Charles it doesn't matter anyway since he's the last. But that now is exactly the game you described.
So your mistake was to see the advantage of having less white balls for the later players, but you didn't take into account the first-mover's advantage that Bruce can only win if Andy hasn't already, and Charles only if neither Andy nor Bruce has.
However so far this only shows that there are two effects working into opposite directions (thus showing that your intuition was based on incomplete analysis of the situation), but it doesn't yet show why those two effects cancel each other out exactly, giving a fair game in the end.
To see that the game is indeed fair, for the moment forget about the colours, and just assume that the balls are numbered $1$ to $4$. Now consider the following questions:
What ball is Andy most likely to draw? Well, obviously he'll draw any ball with equal probability, that is, with probability $1/4$.
What ball is Bruce most likely to draw? Well, he'll draw one of the balls Andy didn't, but since Andy draws any ball with equal probability, each ball will be missing with equal probability, and therefore this doesn't cause any bias; Bruce will again draw any ball with equal probability, $1/4$.
Finally, what ball is Charles most likely to draw? Well, again, no ball is more likely to be missing than any other, so the probabilities are again equal, and every ball has probability $1/4$ to be drawn by Charles.
OK, so now we paint ball $4$ red. But how we paint the balls doesn't affect the probability of the ball being drawn, therefore still Andy, Bruce and Charles each have a probability of $1/4$ to draw the red ball (the remaining $1/4$ is where neither draws the red ball).
Thus they all have equal chances of winning.