Faits: A. A.a. Dans ses plaintes pénales du 7 avril et du 11 mai 2011, C._ (ci-après la partie adverse) a allégué avoir été la victime d'atteintes à l'honneur par le biais de trois sites internet. Il a expliqué que l'une des adresses de ces sites correspondait à une société dirigée par A._ (ci-après le recourant ou le requérant), personne avec qui il était en litige pour des problèmes de bail. Le 10 juin 2011, le Ministère public de la République et canton de Genève, représenté par la Procureure B._, a ouvert une instruction pénale contre inconnu pour diffamation, calomnie et injure (référence P_1). Le 10 novembre 2011, C._ a déposé plainte pénale contre A._ pour insoumission à une décision rendue dans une cause civile les opposant. Le 9 janvier 2012, A._ a porté plainte contre C._ pour gestion déloyale, banqueroute, frauduleuse, diminution effective de l'actif au préjudice des créanciers et violation de l'obligation de tenir une comptabilité (référence P_2). La Procureure B._ a également été chargée de ce dossier. Au cours de l'instruction pénale P_1, il a été procédé à des perquisitions et à des séquestres dans les locaux de la société de A._, ainsi qu'au domicile de ce dernier. C._ et A._ ont été entendus à différentes reprises par la police et/ou la Procureure, soit le 7 juin, le 22 août, le 20 décembre 2011 - date à laquelle A._ a été mis en prévention pour diffamation, voire calomnie, ainsi que pour insoumission à une décision de l'autorité -, le 6 janvier et le 26 septembre 2012. Lors de ces trois dernières séances, le prévenu a fait valoir son droit de se taire. L'inspecteur de la Brigade de criminalité informatique de la police genevoise a été entendu le 25 février, le 2 et le 8 avril 2013. C._ et A._ se sont également déterminés à maintes reprises par écrit, produisant de nombreuses pièces à l'appui de leurs allégations et formulant un certain nombre de réquisitions de preuve. Les deux parties se sont plaintes de la magistrate, en particulier de son inactivité (cf. les courriers des 10 novembre 2011, 9 mars, 23 avril, 8 juin, 19 juin, 4 juillet, 31 août et 24 septembre 2012 pour C._ dans la cause P_1 et des 21 décembre 2011, 14 juin, 2 octobre 2012, 20 février 2013 et 20 mars 2013 pour A._ en référence aux deux procédures pénales), et celle-ci a notamment répondu aux critiques de A._ le 27 mars 2013. A.b. Confirmant les déclarations faites en audience le 2 avril 2013, A._ a déposé le 9 avril 2013 une requête de récusation de la magistrate, ainsi qu'une demande de répétition des actes de procédure accomplis par cette dernière. Il lui a reproché de n'avoir pas instruit à charge et à décharge, ainsi que de n'avoir pas statué sur les actes d'instruction sollicités. La Procureure aurait également violé des règles de procédure en suspendant de facto la cause P_2 sans rendre d'ordonnance et en autorisant l'administration de preuves sur la base d'informations "vraisemblablement illicites". Le requérant a encore allégué que la magistrate n'aurait pas respecté son "droit au silence" en le soumettant à un interrogatoire de plus d'une heure le 26 septembre 2012, attitude constitutive d'une tentative d'intimidation. Il a encore soutenu qu'il ne lui aurait été octroyé que des délais très brefs, que son droit d'accès au dossier aurait été compliqué et que la Procureure n'aurait pas répondu à ses nombreux courriers. La magistrate s'est opposée à cette demande. Quant à C._, il a conclu, sous suite de dépens, à l'irrecevabilité de la requête et, subsidiairement, à son rejet. Le 8 mai 2013, il a chiffré ses prétentions pour la procédure de récusation à 12'888.50 fr. A._ a répliqué le 13, puis le 16 mai 2013, persistant dans ses conclusions et s'opposant à la participation de C._, ainsi qu'à sa requête d'indemnité. B. Par arrêt du 28 mai 2013, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté la requête de récusation et condamné A._ au paiement des frais de procédure (2'105 fr.), ainsi qu'à celui d'une indemnité de 4'000 fr. (TVA en sus) en faveur de C._. Sans déterminer si la requête de récusation concernait l'une ou/et l'autre des deux procédures (P_1 et P_2), la cour cantonale a confirmé la qualité de partie de A._ dans les deux causes, soit en tant que prévenu dans la première et en qualité de plaignant dans la seconde. Elle a également considéré qu'au vu du motif de récusation allégué, elle était en droit de procéder à des actes d'instruction, notamment en recueillant les déterminations de la partie adverse. Les juges cantonaux ont estimé que A._ avait renoncé à demander la récusation de la magistrate après chacune des démarches où il l'en avait menacée et qu'ainsi, seule la lettre de la Procureure du 27 mars 2013 devait être examinée. Or, le contenu de ce courrier démontrait que la magistrate refusait, non pas d'instruire la cause P_2, mais d'entremêler les deux procédures pénales. Se référant ensuite à la procédure P_1, la juridiction précédente a considéré que la requête était infondée, dès lors que les impressions de prévention de la part du Ministère public à l'égard du recourant étaient purement individuelles. C. Par acte du 28 juin 2013, A._ forme un recours en matière pénale, concluant à l'annulation de l'arrêt cantonal et à la récusation de la Procureure. La cour cantonale s'est référée à ses considérants, sans formuler d'observation. Quant au Ministère public, il a conclu au rejet du recours, renvoyant notamment aux déterminations déposées devant l'instance précédente. C._ a conclu à l'irrecevabilité du recours et, à titre subsidiaire, à son rejet. Il a produit une copie du courrier de la Chambre pénale de recours du 16 avril 2013 l'invitant, dans le cadre de la procédure cantonale, à déposer des observations dans un délai de dix jours. Le recourant a persisté dans ses conclusions sans formuler d'observation complémentaire.