Faits : A. A.a. Le 25 avril 2016, l'établissement pénitentiaire CURABILIS a dénoncé pénalement A._, ressortissant algérien sans domicile fixe et sans profession (P1). Il lui était reproché d'avoir, le 21 avril 2016 entre 20h00 et 20h30 à Genève, menacé un gardien de prison et d'avoir intentionnellement bouté le feu, alors qu'il se trouvait dans sa cellule de l'établissement de détention susmentionné, à ses draps et à un linge au moyen d'un briquet/cigarette, objet qu'il avait refusé d'éteindre malgré les injonctions des gardiens. Le prévenu aurait également adopté, lors de l'intervention, un comportement agressif, lançant notamment une chaise contre la porte de sa cellule. Treize personnes avaient été évacuées et il avait été fait appel à la centrale d'engagement des pompiers. A la suite du mandat d'amener délivré contre A._, celui-ci a été appréhendé aux établissements pénitentiaires de la plaine de l'Orbe le 31 mai 2016. Il y purgeait une peine privative de liberté de 14 mois - sous déduction de 97 jours de détention provisoire et d'un jour de détention à titre de réparation morale -, ainsi qu'une peine privative de liberté de 36 mois, sous déduction de 421 jours de détention provisoire et de 5 jours de détention à titre de réparation morale. Selon l'ordre d'écrou du 4 mai 2016, le détenu avait atteint le tiers de sa peine le 13 octobre 2015 et la mi-peine au 23 juin 2016; une éventuelle libération conditionnelle était fixée au 3 mars 2017 et la fin de peine au 24 juillet 2018. Entendu par la police, A._ a reconnu avoir mis le feu à sa cellule; il a en revanche contesté avoir voulu mettre en danger d'autres personnes, avoir adopté un comportement violent vis-à-vis des gardiens et avoir menacé l'un d'entre d'eux. Dans le cadre de l'instruction, une expertise psychiatrique - à laquelle le prévenu s'est opposée - a été ordonnée le 8 juillet 2016. A.b. Le 18 mai 2016, le Centre hospitalier universitaire vaudois (CHUV) a déposé une plainte pénale contre A._ pour dommages à la propriété en raison des dégâts causés par le prévenu lors d'un séjour en mars 2016 dans cet établissement. Vu la procédure déjà ouverte par le Ministère public de la République et canton de Genève, cette cause lui a été transmise par les autorités pénales vaudoises. A.c. Par ordonnance du 1er juin 2016, le Tribunal des mesures de contrainte de la République et canton de Genève (Tmc) a ordonné la détention provisoire de A._ jusqu'au 1er septembre 2016. Cette mesure a été prolongée le 22 août 2016. Le Tmc a retenu l'existence de charges suffisantes, ainsi que des risques de fuite (nationalité étrangère, aucune attache en Suisse, peine-menace concrète) et de récidive (antécédents, facilité à adopter des comportements dangereux et/ou violents, tendances suicidaires alléguées). Le juge de première instance a également considéré qu'aucune mesure de substitution n'était susceptible d'atteindre le but de la détention. A cet égard, il a relevé que si le prévenu continuait à purger la peine de 36 mois fermes prononcée à son encontre en octobre 2015, il passerait sous l'autorité de l'Office d'exécution des peines du canton de Vaud; or, le rapport d'expertise psychiatrique pourrait mettre en lumière une maladie inconnue des autorités ayant prononcé cette sanction, ce qui permettrait au prévenu de demander la révision de son procès, respectivement de saisir la Commission des grâces du Grand Conseil vaudois. B. Le 16 septembre 2016, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours intenté par A._ contre cette ordonnance. Elle a retenu que le prévenu avait purgé la moitié de sa peine, circonstance qui pouvait permettre aux - seules - autorités vaudoises de prononcer un régime d'exécution plus souple (travail externe, congé ou même libération conditionnelle). La cour cantonale a également relevé que, vu l'expertise psychiatrique en cours, la perspective d'une libération conditionnelle restait entière. Il en résultait, selon l'autorité précédente, que l'exécution du solde de la peine n'était pas propre à pallier le risque de fuite ou de récidive, dangers admis par le prévenu; ce dernier pouvait au demeurant voir les jours de détention provisoire subis imputés sur une éventuelle future peine, respectivement sur l'une des sanctions déjà prononcées. C. Par acte du 3 octobre 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, au refus de la prolongation de la détention provisoire et, à titre subsidiaire, à sa remise en détention provisoire si l'exécution de ses peines devait prendre fin avant la clôture de la procédure P1 ou si l'exécution de sa peine ne devait plus se dérouler en milieu fermé. Il sollicite également l'octroi de l'assistance judiciaire. La cour cantonale n'a pas formulé d'observation et le Ministère public n'a pas déposé de déterminations.