What's the best way to remove a wall plug?
I usually just poke them into the wall (unless they are the screw in kind obviously, or the kind with a large collar).  Put a screw driver on them and give it a sharp whack, then patch the hole.  I find it's easier and faster to patch the slightly larger hole, than it is to try and dig them out and then patch the hole anyway.

For the larger collar ones, try to bend/mutilate the collar enough then poke them through the wall.

Be careful when you do this, you don't want to put the screw driver and/or your hand through the wall as well.

In a brick wall you could drill them out.  Find a bit that is about the same size as the hole in the anchor, then carefully drill it out.