I think people who never got captured didn't know that the matrix could be changed, so they just hid from the machines. Then someone figured out that the matrix could be controlled, and the fight to free all began. I think the "freed the first of us" means "freed to believe that the matrix could be defeated".