Faits : A. Le 22 novembre 2010, l'assemblée générale extraordinaire de B._ SA - aujourd'hui en liquidation pour suite de faillite - a été interrompue par une intervention de police; dans le cadre d'une procédure pénale parallèle, celle-ci devait procéder à l'audition de X._, administrateur unique de la société, ainsi que d'Y._, actionnaire. Par l'intermédiaire de son avocat, A._, alléguant détenir 87 % du capital-action de B._ SA, a demandé le 1er décembre 2010 la convocation d'une nouvelle assemblée générale, précisant que, si les autres 13 % étaient réunis, le délai légal de convocation pourrait être abrégé et qu'à défaut, l'assemblée se devrait se tenir avant la fin de l'année en cours. Par courrier du 11 avril 2011, X._ et Y._ ont déposé une plainte pénale contre C._. Ils lui reprochaient d'avoir rédigé le procès-verbal d'une assemblée générale tenue en leur absence le 7 janvier 2011; C._ y avait constaté l'éviction du premier de ses fonctions d'administrateur et sa propre désignation à ce poste, puis avait fait inscrire au Registre du commerce les modifications en découlant. A l'appui de leur plainte, X._ et Y._ ont encore expliqué qu'A._ - qui ne détiendrait que 15 % de B._ SA - n'avait pas obtenu la convocation de l'assemblée générale demandée; son "homme lige", C._, avait alors organisé et tenu une séance lors de laquelle A._ apparaissait frauduleusement comme le détenteur de l'intégralité des actions, ce qui avait permis l'éviction de X._. Ce dernier et Y._ - affirmant chacun détenir 6,5 % du capital - ont saisi la juridiction civile pour faire annuler les décisions prises lors de cette assemblée. Le 12 mai 2011, ils ont en substance complété leur plainte pénale, alléguant qu'A._ aurait également pris leur place au sein d'une société étrangère détenue par B._ SA; cela démontrerait que le susmentionné serait le bénéficiaire, "voire l'instigateur" des actes reprochés à C._. Le Ministère public de la République et canton de Genève a ouvert une instruction pénale contre A._ et C._ le 30 avril 2012 pour faux dans les titres et obtention frauduleuse d'une constatation fausse. A._ a été entendu, en qualité de personne appelée à donner des renseignements, les 26 juin 2012 et 15 avril 2014; il a expliqué qu'il n'était pas présent le 7 juin 2011, que ses avocats avaient tout organisé et que C._ devait parvenir légalement à obtenir la destitution de X._. Quant à C._, auditionné en tant que prévenu, il a reconnu, le 3 septembre 2013 et le 15 avril 2014, avoir convoqué, sur ordre d'A._, l'assemblée générale du 7 janvier 2011, croyant que ce dernier était actionnaire unique, vu qu'il avait libéré l'intégralité du capital-action. Le 27 janvier 2015, le Procureur a avisé les parties qu'il entendait rendre une ordonnance pénale contre C._ pour faux dans les titres et obtention frauduleuse d'une constatation fausse, respectivement une ordonnance de classement s'agissant d'A._. Par décision du 31 août 2015, le Ministère public a classé la procédure contre ce dernier, retenant en substance que rien n'établissait qu'A._ aurait incité C._ à agir par d'autres voies que celles légales. B. Le 11 novembre 2015, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a déclaré irrecevable le recours intenté par X._ et Y._ contre cette décision, considérant que ceux-ci n'étaient pas lésés dans leurs intérêts juridiquement protégés par les infractions dénoncées (art. 251 et 253 CP). C. Par acte du 14 décembre 2015, X._ et Y._ forment un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant, avec suite de frais et dépens, à son annulation, à la reconnaissance de leur qualité de partie, ainsi que de leur intérêt juridiquement protégé à recourir contre l'ordonnance de classement. Ils sollicitent encore le renvoi de la cause à l'autorité précédente et, à titre subsidiaire, au Ministère public afin que celui-ci entreprenne tous les actes d'instruction nécessaires à l'éclaircissement des faits pertinents, rende une ordonnance de condamnation - voire un acte d'accusation - pour instigation à faux dans les titres et obtention frauduleuse d'une constatation fausse à l'encontre d'A._ (ci-après: l'intimé).