Sachverhalt: A. X._ begab sich am 17. November 2012 zu ihrem damaligen Freund A._. Sie führte eine Pistole der Marke "Heckler & Koch" 9mm mit eingesetztem Magazin mit sich, ohne über den erforderlichen Waffentragschein zu verfügen. In der Wohnung von A._ kam es zu einer zunächst verbalen und anschliessend tätlichen Auseinandersetzung, in deren Verlauf X._ die Pistole zog und auf A._ richtete. Nachdem sie eine Ladebewegung gemacht hatte, bewegte sich A._ auf X._ zu, die aus verschiedenen Positionen aus einer Entfernung von mindestens 1.5 Metern insgesamt fünf Schüsse auf diesen abgab. Bei den beiden ersten Schussabgaben stand A._, während er im Moment der dritten bereits stürzte oder schon am Boden lag. Als die Schüsse vier und fünf erfolgten, lag A._ wehrlos auf dem Rücken am Boden. A._ erlitt aufgrund von Durchschüssen insgesamt sieben Schussdefekte und verstarb infolge Verblutens durch die schussbedingten Organverletzungen. B. Das Bezirksgericht Zürich verurteilte X._ am 19. März 2015 wegen vorsätzlicher Tötung im Notwehrexzess und Vergehens gegen das Waffengesetz zu einer Freiheitsstrafe von 5 Jahren. Es sprach der Mutter des Verstorbenen eine Genugtuung von Fr. 10'000.-- zu. Es stellte fest, dass X._ der Mutter des Verstorbenen gegenüber dem Grundsatz nach schadensersatzpflichtig ist und verwies deren Schadensersatzforderungen auf den Zivilweg. Die Kosten der amtlichen Verteidigung von rund Fr. 63'000.-- nahm es (vorläufig) auf die Staatskasse. C. Gegen das erstinstanzliche Urteil erhob die Staatsanwaltschaft am 3. Juli 2015 Berufung; am 13. Juli 2015 erklärte X._ durch ihren amtlichen Verteidiger Anschlussberufung. Mit Präsidialverfügung vom 13. Januar 2016 entliess die Verfahrensleitung des Obergerichts des Kantons Zürich auf Gesuch der neubestellten Wahlverteidigerin von X._, Rechtsanwältin Karen Schobloch, den früheren amtlichen Verteidiger, Rechtsanwalt Marcel Keller. Mit Urteil vom 21. April 2016 sprach das Obergericht X._ vom Vorwurf der vorsätzlichen Tötung frei und verurteilte sie (wegen Vergehens gegen das Waffengesetz) zu einer bedingten Geldstrafe von 80 Tagessätzen zu Fr. 30.-- als Zusatzstrafe zu einer Geldstrafe von 30 Tagessätzen und einer Busse von Fr. 400.--, die beide durch die 93 Tage Untersuchungshaft als geleistet gälten. Die Zivilforderungen der Privatklägerin wies es ab. Das Obergericht auferlegte X._ Untersuchungskosten in Höhe von Fr. 800.-- und nahm die Kosten des erstinstanzlichen Verfahrens und des Berufungsverfahrens, inklusive der Kosten der amtlichen Verteidigung (Fr. 5'000.-- für das Berufungsverfahren) und der unentgeltlichen Vertretung der Privatklägerin, auf die Gerichtskasse. Das Obergericht sprach X._ für das Berufungsverfahren zudem eine Parteientschädigung von Fr. 28'000.-- und eine Genugtuung von Fr. 35'600.-- für entstandene Überhaft zu. D. Die Oberstaatsanwaltschaft des Kantons Zürich führt Beschwerde in Strafsachen und beantragt zusammengefasst, das Urteil des Obergerichts sei aufzuheben und die Sache zur Verurteilung von X._ wegen vorsätzlicher Tötung, begangen im Notwehrexzess, sowie entsprechend zur neuen Beurteilung im Straf-, Kosten- und Entschädigungspunkt an die Vorinstanz zurückzuweisen. Das Obergericht hat auf eine Vernehmlassung verzichtet. X._ beantragt die Abweisung der Beschwerde. Die Oberstaatsanwaltschaft hat sich hierzu nicht geäussert.