Faits : A. Depuis le 15 janvier 2015, A._, né en 1956, fait l'objet d'une enquête pour actes d'ordre sexuel avec un enfant (art. 187 CP), contrainte sexuelle (art. 189 CP) et voies de fait (art. 126 CP). Ces infractions lui sont reprochées en lien avec la garde régulière, effectuée avec son épouse, B._, de l'enfant C._, née en 2005. Le prévenu conteste les faits. La curatrice nommée pour représenter les intérêts de l'enfant, s'est constituée, au nom de celle-ci, partie plaignante. Selon le rapport d'expertise du 16 octobre 2015, les propos de la victime seraient crédibles. Le 7 mars 2016, le prévenu a requis l'audition, en qualité de témoins, de son épouse, ainsi que de sa fille, D._. La Procureure Anne-Laure Huber a entendu, le 16 mars 2016, en tant que témoins, la soeur aînée - majeure - de la victime, ainsi que la femme du prévenu. Au cours de l'audition de cette dernière, celle-ci a été avertie de son obligation de témoigner, de dire la vérité et rendue attentive aux conséquences pénales d'un faux témoignage; la Procureure lui a également rappelé, à trois reprises, ses droits et obligations au sens de l'art. 307 CP. A l'issue de l'audience, la témoin a été informée qu'elle serait convoquée ultérieurement en qualité de prévenue pour faux témoignage et le conseil du prévenu, interpellé par la Procureure, a maintenu sa réquisition de preuve tendant à auditionner la fille de son client. Le 18 mars 2016, A._ a demandé la récusation de la Procureure en charge de l'instruction de son dossier. Celle-ci s'y étant opposée, elle a transmis cette demande à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève qui l'a rejetée le 15 juin 2016. B. Par acte du 17 août 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, à la récusation de la Procureure Anne-Laure Huber, ainsi qu'à l'annulation et à la répétition des actes de procédure auxquels a participé cette dernière. A titre subsidiaire, il demande le renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants. Le recourant sollicite également l'octroi de l'assistance judiciaire. Invitée à se déterminer, la cour cantonale s'est référée à sa décision. Quant à la Procureure intimée, elle a conclu au rejet du recours. Le 31 octobre 2016, le recourant a persisté dans ses conclusions.