Faits: A. Depuis novembre 2011, le Ministère public de la République et canton de Genève instruit une enquête pour escroquerie et blanchiment d'argent contre A._, B._ et C._; au cours de l'instruction, deux autres personnes ont été mises en prévention, soit D._ et E._. La banque X._ s'est constituée partie plaignante dans ladite procédure. Le 18 novembre 2011, un mandat d'amener a été délivré à l'encontre de A._. Sur recours - contre lequel le Procureur s'est pourvu en vain auprès du Tribunal fédéral (cause 1B_724/2012 du 3 décembre 2012) -, A._ a obtenu la délivrance d'un sauf-conduit en vue d'une audience le 24 janvier 2013, ainsi qu'un droit d'accès au dossier à l'issue de cette séance (arrêt cantonal du 21 novembre 2012). Le 3 avril 2013, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a admis le recours interjeté par A._ contre les décisions du Ministère public lui accordant un accès très limité au dossier (29 janvier 2013) et lui refusant l'octroi d'un sauf-conduit pour l'audience prévue le 14 mars 2013 (1 er février 2013). Le 8 avril 2013, A._ a déposé, en parallèle à son recours contre une ordonnance de dépôt du 28 mars 2013, une demande de récusation à l'encontre du Procureur en charge de l'instruction. Ce dernier s'y est opposé. B. Par arrêt du 28 mai 2013, la Chambre pénale de recours a déclaré irrecevable le recours contre l'ordonnance de dépôt et a rejeté la requête de récusation. Elle a en substance retenu que A._ avait identifié au début du mois de février 2013 les motifs dont il se prévalait dans sa requête de récusation, puisqu'il en faisait déjà mention dans ses recours du 1 er et du 7 février 2013. N'ayant alors pas déposé de demande de récusation, il ne pouvait plus s'en prévaloir. Quant au comportement adopté ultérieurement par le Ministère public, la cour cantonale a estimé que celui-ci n'avait plus commis d'erreur susceptible de conduire à une telle sanction, ayant en particulier le droit de convoquer les autres prévenus sans A._ ou son conseil tant qu'une audience de confrontation permettrait ensuite de garantir les droits du prévenu. C. Le 12 juin 2013, A._ forme un recours en matière pénale, concluant à l'annulation de l'arrêt cantonal, à la récusation du Procureur, réservant "l'instruction par l'instance cantonale sur l'annulation des actes d'instruction". Subsidiairement, il requiert le renvoi de la cause à l'autorité précédente pour nouvelle décision, sous réserve de "l'instruction par [celle-ci] sur l'annulation des actes d'instruction". Le recourant conteste le caractère tardif de sa demande de récusation et reproche notamment au Ministère public l'absence de convocation entre novembre 2011 et septembre 2012, le refus de toute consultation du dossier et de l'octroi d'un sauf-conduit en septembre 2012 et les procédures qui s'en sont suivies, la tenue durant seulement trois heures d'une audience le 24 janvier 2013, l'accès ensuite très restreint accordé au dossier malgré deux demandes, le nouveau refus d'un sauf-conduit pour la séance du 14 mars 2013, le défaut de communication de l'annulation de ladite séance et le prononcé d'une ordonnance de dépôt notifiée le 4 avril 2013 sans indiquer qu'il n'était pas obligé de s'y soumettre. La Chambre pénale, ainsi que le Ministère public ont renoncé à formuler des observations.