Faits: Faits: A. A.a Le 15 janvier 1998, D._, née en 1959, a présenté une demande de prestations de l'assurance-invalidité. Elle y indiquait avoir été opérée d'une hernie discale en 1995 et subir depuis le 2 décembre 1997 une incapacité de travail totale dans son activité d'employée de maison qu'elle venait de débuter à 80 % au service de l'Hôpital X._ en raison d'une recrudescence de ses douleurs lombaires. En cours d'instruction de la demande, l'assurée a informé l'Office AI du canton de Neuchâtel (ci-après : l'office AI) qu'elle avait trouvé un autre emploi, également à 80 %, comme gérante de magasin à partir du 16 mars 1998. Par décision du 11 novembre 1998, l'office AI a rejeté la demande de prestations; la décision est entrée en force. A.b Le 2 août 2000, D._ a présenté une nouvelle demande de prestations, invoquant une aggravation de ses problèmes dorsaux. Interpellé par l'office AI, le docteur A._, médecin traitant, a fait état d'une fragilité au niveau de la colonne lombaire en dépit de deux interventions chirurgicales récentes et attesté d'une incapacité de travail de 50 % du 16 août au 15 septembre 1999, puis de 100 % à partir du 11 décembre 1999; il a préconisé un changement d'activité, la station debout exigée dans le secteur de la vente étant contre-indiquée (rapport du 8 novembre 2000). Après avoir appris que l'assurée continuait, malgré son inaptitude à travailler, à participer à des épreuves de course à pied (son sport de prédilection), le docteur B._, médecin-conseil de l'office AI, l'a convoquée pour un entretien personnel à la suite duquel il a mandaté le docteur C._, spécialiste FMH en médecine interne & rhumatologie et titulaire du certificat AMPP en médecine psychosomatique et psychosociale, pour une expertise médicale. Dans son rapport du 24 avril 2001, ce médecin a posé le diagnostic de lombosciatalgies persistantes après double cure de hernie discale L5-S1 droite, status après récessotomie pour racines conjointes L4-L5 et trouble somatoforme douloureux persistant sans comorbidité psychiatrique; selon lui, D._ conservait une capacité de travail entière dans toute activité lui permettant de rester en mouvement. Se fondant sur ces conclusions, l'office AI a rejeté la demande de prestations, au motif que l'assurée ne subissait aucune invalidité significative (décision du 21 août 2001). A.b Le 2 août 2000, D._ a présenté une nouvelle demande de prestations, invoquant une aggravation de ses problèmes dorsaux. Interpellé par l'office AI, le docteur A._, médecin traitant, a fait état d'une fragilité au niveau de la colonne lombaire en dépit de deux interventions chirurgicales récentes et attesté d'une incapacité de travail de 50 % du 16 août au 15 septembre 1999, puis de 100 % à partir du 11 décembre 1999; il a préconisé un changement d'activité, la station debout exigée dans le secteur de la vente étant contre-indiquée (rapport du 8 novembre 2000). Après avoir appris que l'assurée continuait, malgré son inaptitude à travailler, à participer à des épreuves de course à pied (son sport de prédilection), le docteur B._, médecin-conseil de l'office AI, l'a convoquée pour un entretien personnel à la suite duquel il a mandaté le docteur C._, spécialiste FMH en médecine interne & rhumatologie et titulaire du certificat AMPP en médecine psychosomatique et psychosociale, pour une expertise médicale. Dans son rapport du 24 avril 2001, ce médecin a posé le diagnostic de lombosciatalgies persistantes après double cure de hernie discale L5-S1 droite, status après récessotomie pour racines conjointes L4-L5 et trouble somatoforme douloureux persistant sans comorbidité psychiatrique; selon lui, D._ conservait une capacité de travail entière dans toute activité lui permettant de rester en mouvement. Se fondant sur ces conclusions, l'office AI a rejeté la demande de prestations, au motif que l'assurée ne subissait aucune invalidité significative (décision du 21 août 2001). B. D._ a déféré cette décision au Tribunal administratif du canton de Neuchâtel, en demandant un complément d'instruction sous la forme d'une expertise psychiatrique. Par jugement du 29 octobre 2002, le tribunal a admis le recours, annulé la décision litigieuse, et renvoyé la cause à l'office AI pour instruction complémentaire et nouvelle décision, mettant à charge de ce dernier une indemnité de dépens de 800 fr. Par jugement du 29 octobre 2002, le tribunal a admis le recours, annulé la décision litigieuse, et renvoyé la cause à l'office AI pour instruction complémentaire et nouvelle décision, mettant à charge de ce dernier une indemnité de dépens de 800 fr. C. L'office AI interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation. D._ conclut au rejet du recours et sollicite le bénéfice de l'assistance judiciaire. De son côté, l'Office fédéral des assurances sociales propose l'admission du recours.