Sachverhalt: A. X._ erstattete am 30. März 2010 Strafanzeige gegen A._ wegen Ehrverletzung im Sinne von Art. 173 f. StGB. Am 2. Mai 2014 stellte das Bezirksgericht Zürich das entsprechende Verfahren infolge Verjährung ein. Es auferlegte X._ die Gerichtskosten von Fr. 1'500.-- und verpflichtete ihn zur Zahlung einer Prozessentschädigung von Fr. 8'000.-- sowie einer Umtriebsentschädigung von Fr. 500.-- an A._. Die dagegen erhobene Beschwerde von X._ wies das Obergericht des Kantons Zürich am 2. März 2015 ab. B. X._ führt Beschwerde in Strafsachen und beantragt, der Beschluss des Obergerichts des Kantons Zürich vom 2. März 2015 sei (in Bezug auf Ziffer 3 und 4 der erstinstanzlichen Verfügung vom 2. Mai 2014) aufzuheben. A._ sei zur Zahlung der gesamten Gerichtskosten sowie einer Prozessentschädigung und Genugtuung an ihn, X._, zu verpflichten, eventualiter sei er aus der Staatskasse zu entschädigen. X._ stellt ausserdem die Anträge, die zuständige Instanz sei anzuweisen, seine Rechtsverzögerungs- und Rechtsverweigerungsbeschwerde als Aufsichtsbeschwerde zu behandeln, und seine Anzeige gegen die Bezirksrichter wegen Begünstigung von A._ sei vom Obergericht zur Eröffnung einer strafrechtlichen Untersuchung an die zuständige Instanz weiterzuleiten. C. Obergericht und Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. A._ beantragt, auf die Beschwerde sei nicht einzutreten respektive sei diese abzuweisen, soweit darauf eingetreten werde.