Faits: Faits: A. A.a S._, née en 1960, mère de famille, a travaillé comme serveuse à 100 % du 2 juin 1995 au 31 mars 1996, puis à 50 % du mois de juillet 1996 au mois d'avril 1997; elle a travaillé ensuite à 50 % comme repasseuse jusqu'à la fin du mois de novembre 1997. Souffrant de lombosciatalgies, elle a présenté à partir du 2 septembre 1996 - mise à part la période du 16 au 24 novembre où elle fut totalement inapte au travail - une incapacité de 50 %, pour laquelle la Mutuelle Valaisanne lui a versé des indemnités journalières. Mandaté en qualité d'expert, le docteur A._, spécialiste en maladies rhumatismales, a posé les diagnostics de lombosciatalgies bilatérales prédominantes à droite, dorsalgies et état dépressif d'évolution chronique. La capacité de travail de 50 % dans la nouvelle occupation de repasseuse pouvait être augmentée à 100 % dans les deux mois moyennant des exercices quotidiens et ciblés de gymnastique et un traitement antidépresseur (rapport du 28 août 1997). Se fondant sur cette appréciation, la Mutuelle Valaisanne a supprimé ses prestations avec effet au 1er décembre 1997. Sur recours, le Tribunal des assurances du canton de Vaud a condamné l'assurance-maladie perte de gain à indemniser l'intéressée au-delà du 1er décembre 1997 sur la base d'une incapacité de travail de 50 %, jusqu'à rétablissement de la capacité de travail ou au terme des prestations d'assurance (jugement du 31 mars 1999). Parallèlement, l'assurée a bénéficié de prestations de l'assurance-chômage. A.b Le 23 janvier 1997, S._ a déposé une demande de prestations de l'assurance-invalidité tendant à l'octroi d'une rente. L'assurée a effectué elle-même des recherches d'emploi et demandé à faire un stage préalable dans la vente (rapport du 26 février 1998). Du 19 mai 1998 au 5 juillet 1998, elle a accompli un stage dans la société X._, où elle a été engagée le 28 mai 1999 en qualité de caissière auxiliaire à raison de quatre heures par jour, avec un taux d'occupation variable, pour un salaire brut de 16 fr. 90 (17 fr. 05 dès le 1er janvier 2000). Dans un projet de décision du 27 juillet 2000, l'Office de l'assurance-invalidité pour le canton de Vaud (OAI) a fixé le taux d'invalidité de l'assurée à 36,62 % après avoir procédé à la comparaison d'un revenu sans invalidité de 37'050 fr. et d'un revenu d'invalide de 23'481 fr. en fonction d'une incapacité de travail de 50 %. A.c S._ s'est opposée à ce projet de décision en s'appuyant sur une attestation du 22 septembre 2000 (complétée par un rapport du 3 novembre 2000) de la doctoresse G._, médecin-traitant, selon laquelle elle ne présentait plus qu'une capacité de travail de 30 % depuis le 25 septembre 2000. Pour sa part, X._ a confirmé que depuis cette date l'horaire de travail de son employée n'était plus que de deux heures par jour et que le gain correspondant au rendement devrait s'élever à 8 fr. 50 (la moitié du salaire horaire). Dans un rapport du 14 juin 2001 (examen clinique du 29 mai 2001), les médecins du Service médical régional de Y._ (SMR) ont confirmé que l'incapacité de travail de l'assurée n'avait pas varié depuis le 27 juillet 2000. Par décision du 6 juillet 2001, l'OAI a rejeté la demande de rente au motif que le degré d'invalidité résultant de la comparaison des revenus n'ouvrait pas droit à cette prestation. Par décision du 6 juillet 2001, l'OAI a rejeté la demande de rente au motif que le degré d'invalidité résultant de la comparaison des revenus n'ouvrait pas droit à cette prestation. B. S._ a recouru contre cette décision devant le Tribunal des assurances du canton de Vaud en se prévalant, notamment, d'un rapport du 29 juillet 2002 du docteur F._, chef-adjoint au service de rhumatologie, médecine physique et réhabilitation du Centre Hospitalier Z._. Dans le cadre de l'instruction, la juridiction cantonale a confié une expertise au docteur C._, spécialiste en psychiatrie et psychothérapie. Ce médecin a posé le diagnostic de trouble dépressif récurrent, actuellement en rémission (F 33.4), ainsi que celui de syndrome douloureux somatoforme persistant (F 45.4); il a conclu à une incapacité de travail à 30 % (expertise du 11 août 2003). Par jugement du 21 janvier 2004, la juridiction cantonale a admis le recours et réformé la décision entreprise, en ce sens que la recourante avait droit à un quart de rente dès le 1er septembre 2000, à une demi-rente dès le 1er décembre 2000 et à une rente entière dès le 1er mai 2001. Par jugement du 21 janvier 2004, la juridiction cantonale a admis le recours et réformé la décision entreprise, en ce sens que la recourante avait droit à un quart de rente dès le 1er septembre 2000, à une demi-rente dès le 1er décembre 2000 et à une rente entière dès le 1er mai 2001. C. L'OAI interjette recours de droit administratif contre ce jugement dont il requiert l'annulation, en concluant au rétablissement de sa décision du 6 juillet 2001. S._ conclut au rejet du recours, en sollicitant le bénéfice de l'assistance judiciaire gratuite. L'Office fédéral des assurances a renoncé à se déterminer. 