Faits :
A.
Par ordonnance pénale du 1er novembre 2015, A._ a été reconnu coupable d'infraction à l'art. 115 al. 1 let. b et c de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), ainsi que d'empêchement d'accomplir un acte officiel (<ref-law>). Il a été condamné à une peine privative de liberté de 90 jours - sous déduction d'un jour de détention avant jugement - et à une peine pécuniaire de 15 jours-amende à 30 fr. le jour-amende.
Le 11 novembre 2015, agissant par l'intermédiaire de son mandataire, le prévenu a formé opposition contre cette décision. Dans ce même courrier, A._ a requis l'octroi de l'assistance judiciaire. Cette demande a été rejetée le 13 novembre 2015, au motif que la cause ne présentait pas de difficultés particulières en droit ou de fait, qu'elle était de peu de gravité vu les peines encourues et qu'ainsi la désignation d'un avocat d'office ne pouvait être exigée. Le recours intenté par le prévenu le 26 novembre 2015 contre cette décision a été rejeté le 21 mars 2016 par la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
B.
Par acte du 3 mai 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, à l'octroi de l'assistance judiciaire et à la nomination de Me Arnaud Moutinot en tant que défenseur. A titre subsidiaire, il demande le renvoi de la cause au Ministère public pour nouvelle décision. Le recourant sollicite également le bénéfice de l'assistance judiciaire.
Invités à se déterminer, le Ministère public a conclu au rejet du recours, tandis que la cour cantonale a renoncé à formuler des observations.

Considérant en droit :
1.
Le recours en matière pénale est ouvert contre une décision incidente par laquelle l'assistance judiciaire gratuite est refusée à une partie à la procédure pénale (<ref-law>). Le refus de désigner un avocat d'office est susceptible de causer au prévenu un préjudice irréparable au sens de l'<ref-law>, de sorte qu'il peut faire l'objet d'un recours immédiat au Tribunal fédéral (<ref-ruling> consid. 2.2 p. 205; <ref-ruling> consid. 4 p. 338 s. et les références).
Pour le surplus, le recours a été formé en temps utile (art. 46 al. 1 let. a et 100 al. 1 LTF) contre une décision rendue en dernière instance cantonale (<ref-law>) et les conclusions présentées sont recevables au regard de l'<ref-law>. Il y a donc lieu d'entrer en matière.
2.
Selon l'<ref-law>, la direction de la procédure ordonne une défense d'office si le prévenu ne dispose pas des moyens nécessaires et si l'assistance d'un défenseur est justifiée pour la sauvegarde de ses intérêts. Cette seconde condition est remplie notamment lorsque l'affaire n'est pas de peu de gravité et qu'elle présente, sur le plan des faits ou du droit, des difficultés que le prévenu seul ne pourrait pas surmonter (<ref-law>); ces deux conditions doivent être réunies cumulativement.
En tout état de cause, une affaire n'est pas de peu de gravité lorsque le prévenu est passible d'une peine privative de liberté de plus de quatre mois, d'une peine pécuniaire de plus de 120 jours-amende ou d'un travail d'intérêt général de plus de 480 heures (<ref-law>).
3.
Laissant indécise la question de l'indigence du prévenu, la Chambre pénale de recours a rappelé les peines prononcées - non définitives - à l'encontre du recourant (90 jours de peine privative de liberté [art. 115 al. 1 let. b et c LEtr] et 15 jours-amende [<ref-law>]). Elle a ensuite relevé que, même en tenant compte d'un éventuel risque d'aggravation de la quotité de ces sanctions devant le tribunal de première instance, la peine concrètement encourue par le recourant restait moins élevée que celles indiquées à l'<ref-law>; la cause étant ainsi de peu de gravité, l'une des conditions posées par l'<ref-law> n'était pas réalisée. La cour cantonale a encore indiqué que les circonstances d'espèce ne présentaient pas de difficultés particulières en fait ou en droit que le recourant ne pourrait résoudre seul. A cet égard, elle a précisé que, vu les autres délits retenus en sus de celui à l'art. 115 al. 1 let. b LEtr, le recourant était soustrait à l'application de la directive du Parlement européen et du Conseil de l'Union européenne du 16 décembre 2008 sur le retour, son éventuelle condamnation à une peine privative de liberté n'étant ainsi pas contraire à cette réglementation. Selon l'autorité précédente, la cause ne pouvait être qualifiée de complexe du seul fait de la contestation des faits à l'origine du chef de prévention d'empêchement d'accomplir un acte officiel.
4.
Ce raisonnement ne prête pas le flanc à la critique et le recourant ne développe aucune argumentation propre à le remettre en cause. En particulier, la sanction encourue dans un cas concret ne correspond pas nécessairement à la peine menace découlant des infractions reprochées (cf. <ref-law>) ou à la quotité des peines indiquée à l'<ref-law> (arrêts 1B_366/2015 du 16 novembre 2015 consid. 4; 1B_201/2015 du 1er septembre 2015 consid. 2; 1B_138/2015 du 1er juillet 2015 consid. 2.2 et 2.3; 1B_203/2014 du 2 octobre 2014 consid. 2.2). Certes, tout risque d'aggravation de la peine par le juge de première instance ne peut être exclu (arrêts 1B_138/2015 du 1er juillet 2015 consid. 2.2; 1B_67/2015 du 14 avril 2015 consid. 2.2; 1B_203/2014 du 2 octobre 2014 consid. 2.2). Toutefois, la sanction retenue dans l'ordonnance pénale - inférieure en l'espèce à celles posées à l'<ref-law> - constitue, à l'instar de ce qui prévaut en matière d'appel contre une condamnation de première instance, un indice important quant à la peine susceptible de devoir finalement être exécutée (<ref-ruling> consid. 3.1 p. 275; arrêts 1B_201/2015 du 1er septembre 2015 consid. 2; 1B_138/2015 du 1er juillet 2015 consid. 2.2). Cela vaut d'ailleurs d'autant plus en l'occurrence qu'après avoir entendu le recourant le 7 décembre 2015 et les policiers dénonciateurs le 13 janvier 2016, une ordonnance pénale sur opposition - également ensuite contestée et qui équivaut donc à un acte d'accusation (art. 356 al. 1 et 326 al. 1 let. f CPP) - a été rendue par le Ministère public le 27 janvier 2016 condamnant le recourant aux mêmes sanctions que celles prononcées en novembre 2015 (art. 115 al. 1 let. a et b LEtr et 286 CP). En tout état de cause, il sied de relever que le recourant ne se prévaut pas, devant le Tribunal fédéral, de ces mesures d'instruction - ultérieures à son recours cantonal relatif à l'assistance judiciaire, mais antérieures au prononcé attaqué - et auxquelles a participé son mandataire pour démontrer la nécessité d'un mandataire d'office.
La cour cantonale a ensuite rappelé à juste titre que la directive sur le retour ne s'appliquait pas lorsque d'autres délits que le séjour irrégulier étaient retenus à l'encontre du prévenu (arrêts 1B_270/2015 du 25 août 2015 consid. 3; 1B_68/2015 du 29 avril 2015 consid. 2.3; 1B_67/2015 du 14 avril 2015 consid. 2.3; 6B_320/2013 du 29 août 2013 consid. 3.2); tel était le cas en l'espèce vu en particulier la condamnation pour empêchement à accomplir un acte officiel figurant notamment dans l'ordonnance pénale de novembre 2015. Ce même motif dispensait d'ailleurs le Ministère public de s'enquérir, à ce stade de la procédure, du dossier administratif relatif au recourant (arrêts 1B_67/2015 du 14 avril 2015 consid. 2.3; 1B_231/2014 du 8 août 2014 consid. 2.3). Au demeurant, la Procureure n'a pas manqué de le faire lorsque le recourant a contesté, pour la première fois (cf. l'absence de motivation dans son opposition), les faits en lien avec ce chef de prévention lors de son audition du 7 décembre 2015 (cf. la demande du 9 décembre 2015 de la magistrate et la réponse y relative du 15 suivant du Service des migrations de la République et canton de Neuchâtel; <ref-law>). Dès lors que ces éléments figurent au dossier, le juge de première instance ne manquera pas, le cas échéant, d'en tenir compte.
Partant, la Chambre pénale de recours n'a pas violé le droit fédéral en confirmant le rejet de la demande d'assistance judiciaire.
5.
Il s'ensuit que le recours est rejeté.
Cette issue était d'emblée prévisible, ce qui conduit au rejet de la demande d'assistance judiciaire (<ref-law>). Vu les circonstances, il se justifie exceptionnellement de statuer sans frais (<ref-law>). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La requête d'assistance judiciaire est rejetée.
3.
Il n'est pas perçu de frais judiciaires, ni alloué de dépens.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public de la République et canton de Genève et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 21 juillet 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant : Eusebio
La Greffière : Kropf