Faits : A. A.a. Le 19 janvier 2012, X._ a cambriolé, en compagnie de B._, l'appartement de C._, née en 1925. X._ est parvenu à soustraire 1500 fr. à la victime, des bijoux et sa carte de crédit, après l'avoir réveillée et avoir placé un couteau près de sa gorge, tout en la menaçant pour obtenir le code de la carte. X._ a ensuite procédé à plusieurs retraits pour un montant total de 5000 fr. Les bijoux dérobés ont été vendus le 19 janvier 2012 dans une bijouterie genevoise pour un montant de 490 francs. A.b. En date du 18 février 2012, au soir, X._ s'est introduit de force dans l'appartement d'A._, née en 1933, dans le bu t de la dépouiller. Il a agi de concert avec D._, qui, en bref, avait effectué les repérages nécessaires et fourni un couteau et des gants à X._, tout en le laissant agir seul pour ne pas être reconnu. Muni dudit couteau, dont la lame mesurait une vingtaine de centimètres, il a menacé sa victime en plaçant l'arme sous la gorge de cette dernière. Au cours de l'agression, il a également exercé une très forte pression sur sa gorge, au point qu'elle a cru mourir asphyxiée. Il l'a dépouillée de ses bijoux et l'a contrainte à révéler le code de sa carte bancaire, avant de la forcer à le suivre dans la salle de bains, de la ligoter en serrant très fortement ses liens, de la pousser dans la baignoire et de la bâillonner de telle façon qu'elle a rencontré les plus grandes difficultés à respirer. Il l'a ensuite abandonnée dans cette posture en verrouillant la porte de la salle de bains, poussant encore le volume de la télévision. L'agression a duré au total 45 minutes. A dire d'expert, la vie d'A._ a été concrètement mise en danger et elle a eu beaucoup de chance de s'en tirer, compte tenu d'un risque d'anoxie cérébrale et d'une situation potentielle de " décompensation catastrophique " auxquels elle avait été exposée, synonyme de risque clair de décès en raison d'un possible arrêt circulatoire ou cardiorespiratoire. B. En raison de ces faits notamment, le Tribunal criminel du canton de Genève a, par jugement du 6 décembre 2013, acquitté X._ du chef de séquestration aggravée (art. 183 ch. 1 et 184 CP), mais l'a reconnu coupable de tentative d'assassinat (art. 22 al. 1 CP cum art. 112 CP), de brigandages aggravés (art. 140 ch. 1, 2 et 3 CP), d'utilisation frauduleuse d'un ordinateur (art. 147 al. 1 CP), de vol (art. 139 ch. 1 CP), de dommages à la propriété (art. 144 al. 1 CP), de dommages à la propriété de peu de gravité (art. 144 al. 1 CP cum art. 172 ter CP), de recel (art. 160 ch. 1 CP), de violences contre les autorités et les fonctionnaires (art. 285 ch. 1 CP) et d'entrée et séjour illégaux (art. 115 al. 1 let. a et b LEtr). Il l'a condamné à une peine privative de liberté de 13 ans, sous déduction de 658 jours de détention avant jugement. C. Statuant sur appel de X._, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a, par arrêt du 28 août 2014, annulé le jugement de première instance, notamment en ce qu'il reconnaissait X._ coupable de tentative d'assassinat et de brigandage aggravé au sens de l'art. 140 ch. 1, 2 et 3 CP. Statuant à nouveau, elle l'a reconnu coupable de brigandage aggravé au sens de l'art. 140 ch. 4 CP en relation avec l'agression d'A._ et au sens de l'art. 140 ch. 3 CP par rapport à celle de C._. Elle a confirmé la peine privative de liberté de 13 ans prononcée en première instance. X._ et le Ministère public ont chacun formé recours contre cet arrêt devant le Tribunal fédéral. D. Postérieurement au dépôt des recours devant la cour de céans, la cour cantonale a informé les parties et le Tribunal fédéral par p li du 17 février 2015 que l'un des juges assesseurs ayant participé à la procédure d'appel ne remplissait alors plus les conditions d'éligibilité prescrites par l'art. 10 de la loi genevoise sur l'organisation judiciaire (LOJ/GE; RS/GE E 2 05), en raison d'un dépassement de la limite d'âge. Par acte du 27 mars 2015, X._ a déposé auprès de la cour cantonale une demande de révision de l'arrêt du 28 août 2014, concluant en substance à son annulation et à ce que la procédure d'appel soit recommencée ab ovo. Il a simultanément sollicité la suspension de la procédure fédérale. Par ordonnance du 2 avril 2015 (6B_1182/2014, 6B_1200/2014, et 6B_1201/2014), le Président de la cour de céans a ordonné la suspension des procédures pendantes devant le Tribunal fédéral. Le Ministère public, qui avait recouru au Tribunal fédéral pour obtenir une condamnation du recourant pour tentative d'assassinat en concours avec la qualification de brigandage aggravé au sens de l'art. 140 ch. 4 CP, n'a déposé aucune demande de révision. Il s'en est remis à justice s'agissant de la demande de révision du recourant. Par arrêt du 27 juillet 2015, l'autorité précédente a fait droit à la demande de révision du recourant, renvoyant la cause afin de procéder à de nouveaux débats et de rendre une nouvelle décision. Par ordonnance du 23 octobre 2015, le Président de la cour de céans a rayé du rôle les procédures de recours fédérales, qui étaient devenues sans objet en raison de l'arrêt précité. E. Dans un nouvel arrêt daté du 18 novembre 2015, la cour cantonale a partiellement admis l'appel de X._ contre le jugement du Tribunal criminel du 6 décembre 2013. Elle a confirmé sa condamnation pour tentative d'assassinat, mais a annulé ce jugement en tant qu'il l'avait reconnu coupable de brigandage qualifié au sens de l'art. 140 ch. 1, 2 et 3 CP et l'avait condamné à une peine privative de liberté de 13 ans, sous déduction de la détention avant jugement. Statuant à nouveau, l'autorité précédente l'a reconnu coupable de brigandage qualifié au sens de l'art. 140 ch. 3 CP en relation avec l'agression d'A._ et au sens de l'art. 140 ch. 2 CP par rapport à celle de C._, le condamnant à une peine privative de liberté de 12 ans, sous déduction de 1370 jours de détention avant jugement. F. Contre cet arrêt, X._ dépose un recours en matière pénale au Tribunal fédéral. Il conclut à l'annulation de l'arrêt attaqué et à sa réforme, en ce sens qu'il soit acquitté de l'infraction de tentative d'assassinat, ainsi qu'au renvoi de la cause pour nouvelle décision, en particulier sur la peine. Il sollicite également l'octroi de l'assistance judiciaire. G. Invités à se déterminer, le Ministère public a conclu au rejet du recours, tandis que la cour cantonale a intégralement persisté dans les termes de son arrêt du 18 novembre 2015. La réplique du recourant a été communiquée aux parties. La partie plaignante a déclaré s'en rapporter à justice.