Faits: A. S._, ressortissante espagnole née en 1962, a travaillé en qualité d'aide de cuisine pour la clinique G._. Souffrant de problèmes pulmonaires et d'obésité, elle s'est trouvée en incapacité de travail depuis le mois de mars 2006, puis a déposé une demande de prestations de l'assurance-invalidité le 6 novembre 2006. Par décision du 22 février 2008, l'Office cantonal de l'assurance-invalidité du canton de Genève (l'office AI) a rejeté la demande. Dans le cadre du recours formé contre cette décision devant le Tribunal cantonal des assurances sociales de la République et canton de Genève, le dossier a été complété par un rapport de l'Hôpital X._ du 11 mars 2008 ainsi que par un avis médical du SMR du 2 juin 2008. Le SMR a constaté que la capacité de travail de l'assurée restait entière dans une activité respectant ses limitations fonctionnelles (déplacements, port de charges de plus de 2 kg). Pendente lite, l'office AI a annulé sa décision. Le 17 juin 2008, le tribunal cantonal a rayé la cause du rôle et renvoyé celle-ci à l'office AI afin qu'il procède au calcul du taux d'invalidité de l'assurée. Par décision du 28 janvier 2009, l'office AI a fixé le degré d'invalidité de S._ à 16,6 % et refusé en conséquence de la mettre au bénéfice de mesures d'ordre professionnel de l'AI. B. S._ a recouru contre cette décision en concluant principalement à l'octroi de mesures d'ordre professionnel, subsidiairement à l'allocation d'une rente entière d'invalidité. Par jugement du 21 avril 2009, la juridiction cantonale a porté le taux d'invalidité de l'assurée de 17 % à 21 %. Elle a dès lors admis le recours, annulé la décision administrative du 28 janvier 2009, et renvoyé la cause à l'office AI afin qu'il mette en oeuvre sans délai des mesures de réadaptation professionnelle. Par ailleurs, le tribunal cantonal a fixé l'indemnité de dépens à 2'500 fr. et l'émolument de justice à 750 fr. C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, en concluant à la confirmation de sa décision du 28 janvier 2009. L'intimée conclut au rejet du recours, avec suite de dépens. De son côté, l'Office fédéral des assurances sociales en propose l'admission. Par ordonnance du 30 octobre 2009, le Juge instructeur a admis la requête d'effet suspensif au recours présentée par l'office AI.