Faits: A. Par jugement du 18 octobre 2007, le Tribunal du IIIème arrondissement pour le district de Monthey a libéré A._ de la prévention d'actes d'ordre sexuel au préjudice de sa fille X._, née en 1998, et de sa belle-fille C._, née en 1988. B. Statuant sur appels des parties civiles par jugement du 15 juin 2009, le Tribunal cantonal du canton du Valais a acquitté A._ de toute infraction à l'encontre de X._. Par contre, il l'a condamné à une peine privative de liberté de sept mois avec sursis pendant deux ans aux chefs d'actes d'ordre sexuel et tentative d'actes d'ordre sexuel au détriment de C._. Pour l'essentiel, les juges d'appel ont retenu les éléments suivants. B.a Au printemps 2001, C._ a révélé à sa maman, B._, qu'au cours des mois de mai et juin 2001, son beau-père avait agi de manière déplacée à son encontre en lui ayant caressé la poitrine par-dessus ses sous-vêtements, attouché le sexe et les fesses en la frôlant dans le corridor de l'appartement et essayé de l'embrasser sur la bouche. Informée par B._, D._, psychologue de C._, a entendu la fillette qui lui a répété les confidences faites à sa mère. Alerté par lettre du 2 novembre 2001 de D._, le Service cantonal de la jeunesse a dénoncé le cas à l'autorité pénale par courrier du 24 janvier suivant. B.b A._ ayant été convoqué par la police pour le 19 février 2002, B._, qui redoutait la réaction de ce dernier, a mis en garde ses enfants aînés. Ayant surpris leur conversation, X._ a interrogé sa maman qui lui a répondu:"X._, pour l'instant, tu es trop petite pour savoir, mais je t'expliquerai quand tu seras plus grande. Il a fait quelque chose de pas joli à C._". X._ a alors déclaré: "Ah, à elle aussi, il a fait quelque chose de pas joli, à C._... il a mis le doigt dans le trou où je fais caca et il a mis le doigt dans la bouche et il a mis le doigt où je fais pipi". Par la suite, elle a ajouté qu'il "s'était planté un truc grand dans le zizi", que "c'était beaucoup de fois qu'il avait planté dans le trou du caca et dans le trou du pipi", qu'elle "avait mal", que "c'était pas rigolo", que "papa il était méchant", que "ça s'était passé dans la salle de bains et dans la chambre où A._ dormait". B.c En raison de ces révélations, X._ a fait l'objet d'un examen médical approfondi le 27 février 2002. Selon les constatations du docteur E._ (spécialiste en pédiatrie), elle n'avait plus d'hymen et présentait sur tout le pourtour de l'orifice vaginal - bien ouvert - un petit bourrelet épaissi et fibreux, séquelles compatibles avec des pénétrations répétées (rapports des 7 juin 2002 et 10 mars 2004). B.d Le 17 juin 2002, elle a été entendue par une inspectrice de police. D'une durée de onze minutes, l'audition a été filmée et l'entretien consigné par écrit le jour même. Aux termes d'observations formulées à la demande de A._, F._ (psychologue et psychothérapeute FSO, certifiée LAVI) a indiqué que la durée de l'audition de X._ par la police semblait courte. L'entrée en matière et les premiers contacts avec l'enfant étaient néanmoins adéquats. Cette dernière était cohérente dans ses réponses et mature pour son âge. A priori, il n'apparaissait pas que des erreurs fondamentales dans le choix des questions soumises à l'enfant s'y soient glissées, même si certaines, d'ordre essentiel, pouvaient manquer. La présence de nombreux silences et hésitations laissait par exemple inférer un malaise de l'enfant envers son père, trouble qui n'avait pas été suffisamment exploré. S'il était perceptible que X._ devait raconter à la police, probablement sur injonction de la mère, il n'en résultait pas pour autant qu'elle n'avait pas vécu d'attouchements sexuels (courrier du 4 septembre 2004). B.e Par la suite, X._ a été conduite auprès d'une spécialiste en psychiatrie infantile. Dans un rapport daté du 17 décembre 2002, la doctoresse G._ a indiqué que X._ lui avait parlé de son papa qui était parti en Afrique, qu'elle n'aimait plus, qui avait été méchant avec elle et qui lui avait mis le doigt dans son "tutu". Elle avait également évoqué ses poupées qui n'avaient "que des mamans". A la question de savoir si elle connaissait des messieurs qui n'étaient pas gentils, elle s'était tortillée sur sa chaise, avait tourné le dos à la doctoresse et répondu que son papa n'était pas gentil avec elle, qu'il était méchant, qu'il tapait tout le monde et faisait d'autres choses dont elle ne souhaitait pas parler. La doctoresse G._ a également rapporté que X._ avait été hospitalisée en novembre 2002 dans le service du docteur E._. Ce dernier avait observé que, de manière inhabituelle chez un enfant, la fillette qui se plaignait de douleurs abdominales lui avait montré son bas-ventre. En outre, lorsqu'après quelques jours, le docteur E._ lui avait annoncé son prochain retour à la maison, elle s'était instantanément refermée et avait déclaré ne pas vouloir rentrer. Selon la psychiatre, elle associait son retour à la maison au souvenir de ce qui s'y était passé avec son père. B.f Afin de déterminer la crédibilité des déclarations de C._ et X._, le président du tribunal d'arrondissement a confié un mandat d'expertise au docteur H._ (psychiatre et psychothérapeute FMH pour enfants et adolescents). Après avoir entendu une fois chaque enfant, l'expert a conclu, le 24 janvier 2003, à la crédibilité de leurs révélations. A la suite des critiques formulées contre ce rapport (cf. courrier du 22 décembre 2004 de K._ [spécialiste en psychologie]), le juge de district de Monthey a ordonné le 14 mars 2005 une seconde expertise confiée à la doctoresse L._ (psychiatre et psychothérapeute pour enfants et adolescents). Celle-ci s'est entretenue avec X._ à cinq reprises, C._ à deux reprises, B._ et A._ à deux reprises chacun. Aux termes du rapport déposé le 15 août 2006, les révélations de C._ étaient probablement partiellement crédibles. En revanche, celles de X._ présentaient essentiellement les caractéristiques des fausses allégations que l'on reconnaît chez les jeunes enfants pris dans des divorces conflictuels. S'agissant des constatations du docteur E._, l'experte a expliqué qu'il pouvait arriver qu'un enfant de deux ans, confronté à de la violence domestique et des séparations familiales brutales, recoure à des actes d'auto-masturbation apaisante. B.g En réponse à ces dernières conclusions, plusieurs nouveaux rapports médicaux ont été produits au dossier. Selon celui établi le 5 mai 2008 par les docteurs M._ et N._ du Centre hospitalier universitaire vaudois (CHUV, Service de pédiatrie de l'Hôpital de l'Enfance de Lausanne), les constatations du docteur E._ évoquaient clairement une morphologie hyménéale modifiée compatible avec une anamnèse de pénétration ou de tentative de pénétration vaginale. Si ces lésions résultaient de masturbation, elles impliquaient nécessairement une pénétration avec les doigts ou des objets, agissements que la littérature spécialisée considérait comme caractéristiques d'abus sexuels. En effet, la masturbation infantile ne provoquait pas, en règle générale, des blessures de ce genre. De son côté, le docteur E._ a observé que les comportements de masturbation habituellement évoqués par les parents se résumaient à des caresses et stimulations clitoridiennes. A sa connaissance, les enfants de l'âge de X._ ne s'adonnaient pas à des gestes impliquant une pénétration manuelle. Si, dans de rares cas, il avait pu constater l'introduction de petits objets dans le vagin, ceux-ci n'en avaient pour autant jamais endommagé l'hymen (rapport du 29 septembre 2008). Enfin, aux termes d'un avis daté du 19 novembre 2008, la doctoresse P._ (psychiatre et psychothérapeute de X._) a indiqué qu'il était hautement invraisemblable que celle-ci se soit infligée de telles lésions par auto-masturbation apaisante. Par définition, de tels comportements étaient agréables et cessaient aussitôt qu'ils entraînaient douleur ou inconfort, soit bien avant de provoquer des blessures, à plus forte raison, une déchirure de l'hymen ou des boursouflures cicatricielles. Infligées à soi-même, des lésions pareilles relevaient bien plutôt de l'auto-mutilation. Or, celle-ci n'était observée qu'auprès d'enfants gravement carencés, déficitaires, atteints de psychose ou d'adolescents souffrant de troubles graves du comportement, ce qui ne correspondait pas au profil de X._. C. A._, d'une part, et X._ ainsi que Yannis Sakkas, d'autre part, interjettent recours en matière pénale. Le premier conclut à son acquittement de toute infraction. La deuxième requiert principalement la condamnation du prénommé pour actes d'ordre sexuel commis à son préjudice et l'octroi d'une indemnité pour tort moral d'un montant de 10'000 francs. A titre subsidiaire, elle réclame le renvoi de la cause à l'autorité cantonale pour complément d'instruction et nouveau jugement. Le troisième réclame une indemnité de dépens pour l'instance d'appel de 3600 francs. A._ et X._ sollicitent, en outre, le bénéfice de l'assistance judiciaire gratuite. Invités à se déterminer sur le recours de X._, A._ a conclu au rejet de ce dernier ainsi qu'à l'octroi de l'assistance judiciaire. De leur côté, le Ministère public du canton du Valais a renoncé à produire des observations, tandis que la cour cantonale s'est référée aux considérants de son arrêt. 