Faits : A. A._, ressortissant bolivien né en 1972, a contracté mariage le 10 septembre 2004 à X._ avec B._, ressortissante suisse née en 1980. Par requête du 12 novembre 2007, A._ a demandé la naturalisation facilitée qu'il a obtenue le 27 octobre 2008 - décision entrée en force le 28 novembre 2008 -, après avoir co-signé avec son épouse le 8 septembre 2008 une déclaration confirmant la stabilité et l'effectivité de la communauté conjugale. Le 17 juin 2009, les époux A._ et B._ ont déposé une requête commune de divorce, assortie d'une convention sur les effets accessoires signée le 5 mai 2009. Le divorce a été prononcé par jugement du 11 novembre 2009, décision devenue exécutoire le 24 novembre suivant. A._ s'est remarié le 5 février 2010 avec une ressortissante cubaine. B. A la suite d'un courrier du Service de la population du canton de Vaud (SPOP), l'Office fédéral des migrations (ODM) a informé l'intéressé le 23 mars 2010 qu'il devait examiner s'il y avait lieu d'annuler la naturalisation facilitée compte tenu de la signature de la déclaration commune en septembre 2008, de la rencontre avec sa future seconde épouse en janvier 2009, de la requête de divorce introduite en juin 2009, du divorce prononcé en novembre 2009 et de son remariage intervenu en février 2010. A._ a exposé que les difficultés conjugales n'étaient apparues qu'en janvier 2009 et que, lors de la signature de la déclaration commune, les époux vivaient en communauté conjugale effective et stable. Il a également souligné la durée de son séjour en Suisse, ainsi que son intégration socio-professionnelle réussie. Par courrier du 21 mai 2010, A._ a complété ses déterminations en reprenant pour l'essentiel les arguments avancés précédemment, insistant en particulier sur la durée de son séjour en Suisse qui lui permettrait d'obtenir la naturalisation ordinaire. Par écrit daté du 23 avril 2010, puis du 15 septembre 2010, B._ a indiqué en substance qu'elle n'entendait pas répondre aux questions qui lui avaient été adressées par l'ODM car les circonstances de son divorce relevaient de sa sphère privée; elle a cependant notamment mentionné dans son second courrier que le mariage avait été célébré le 10 septembre 2004 à X._ en présence de 200 personnes et que ses souvenirs étaient confus. Finalement, sur réquisition de l'ODM et du SPOP, B._ a été entendue par la police le 27 mai 2011, en présence de son ex-conjoint et du mandataire de ce dernier. Elle a certifié qu'au moment de la signature de la déclaration de la vie commune leur communauté conjugale était effective et stable. Interrogée sur la fin de leur vie commune, elle a indiqué que son couple avait rencontré des difficultés dès janvier 2009, soit quand elle s'était rendue compte que son époux entretenait une liaison avec une femme rencontrée à Cuba lors de vacances. Invité à se déterminer sur l'audition de son ex-épouse, A._ a pris position le 5 décembre 2011, reprenant pour l'essentiel les arguments avancés dans son courrier du 21 mai 2010. A la suite de la production au dossier d'une lettre déposée au SPOP par l'épouse actuelle de A._ dans le cadre de ses démarches de régularisation auprès de cet office, l'intéressé a réaffirmé avoir rencontré celle-ci pour la première fois au début de l'année 2009. Il a également soutenu que les contacts préalables sur internet ne constituaient pas un élément permettant de remettre en cause la stabilité de l'union conjugale existante en particulier lors de la signature de la déclaration commune à l'automne 2008. Par décision du 16 octobre 2012, l'ODM a prononcé, avec l'assentiment des autorités cantonales compétentes des cantons de Vaud et Genève, l'annulation de la naturalisation facilitée accordée à A._. Selon cet office, la nationalité avait été obtenue sur la base de déclarations mensongères, voire une dissimulation de faits essentiels; par ailleurs, aucun des éléments contenus dans les déterminations de l'intéressé n'était susceptible de l'amener à modifier son point de vue. C. Par arrêt du 26 juin 2013, le Tribunal administratif fédéral a rejeté le recours intenté par A._ contre cette décision. L'instance précédente a considéré que le droit d'être entendu de celui-ci n'avait pas été violé car l'audition de B._, entendue à titre de tiers appelé à fournir des renseignements, était conforme aux exigences de l'art. 18 al. 1 et 19 PA (RS 172.021); elle a également souligné que le refus de l'ODM de donner à son mandataire les directives réglant la conduite des auditions des ex-conjoints n'était pas contraire au droit d'être entendu dans la mesure où il s'agissait de documents de travail internes à l'administration et qui n'avaient pas servi de base à la décision querellée. Sur le fond, cette autorité a jugé que l'enchaînement chronologique des faits et le court laps de temps les séparant étaient de nature à fonder la présomption de fait selon laquelle, au moment de la signature de la déclaration commune et lors de la décision de naturalisation, A._ n'avait plus la volonté de maintenir une communauté stable. En outre, les premiers juges ont relevé que la rencontre de l'intéressé avec sa conjointe actuelle ne pouvait être considérée comme un fait extraordinaire susceptible d'expliquer la détérioration de l'union conjugale. D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt et, subsidiairement, de renvoyer la cause à l'autorité précédente ou à l'ODM pour nouvelle décision. Il se plaint de violations de l'art. 49 let. c PA - estimant que l'autorité aurait dû prendre sa décision en opportunité -, du principe de la proportionnalité - soutenant à cet égard que l'autorité aurait abusé de son pouvoir d'appréciation -, et de son droit d'être entendu, relevant que l'autorité aurait dû motiver sa décision en lien avec l'art. 49 let. c PA. Il invoque également la violation de l'art. 41 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (loi sur la nationalité, LN; RS 141.0). Il sollicite en outre l'octroi de l'effet suspensif. Invité à se déterminer, l'ODM a confirmé sa position, relevant que les arguments avancés par le recourant relatifs à son intégration en Suisse étaient sans pertinence dans la mesure où l'examen était limité aux conditions dans lesquelles l'intéressé avait obtenu la naturalisation facilitée. Quant à l'autorité précédente, elle a renoncé à formuler des observations. Par ordonnance du 2 octobre 2013, le Président de la Ire Cour de droit public a accordé l'effet suspensif au recours.