Faits :
A.
A.a. Le 20 mars 2017, à la requête de A._, le Tribunal de première instance de Genève a ordonné, à concurrence de 116'535 fr. 30 plus intérêts à 5% dès le 1er août 2016, le séquestre des droits de B._ dans la société simple gérant le restaurant X._, des revenus perçus par B._ dans l'exploitation dudit restaurant, des comptes bancaires dont B._ est titulaire auprès de la Banque C._ à U._, des parts de B._ dans la société D._ Sàrl en liquidation et de la créance en distribution des deniers de B._ contre la masse en faillite de ladite société.
A.b. Le 12 juin 2018, suite à une plainte formée avec succès contre un premier procès-verbal de séquestre dressé le 6 novembre 2017, l'Office des poursuites de Genève (ci-après: l'Office) a adressé à A._ un nouveau procès-verbal, constatant derechef le non-lieu de séquestre de salaire de B._ dans l'exploitation du restaurant X._.
A.c. Par acte déposé le 10 juillet 2018 à la Chambre de surveillance des Offices des poursuites et faillites de la Cour de justice du canton de Genève (ci-après: Chambre de surveillance), A._ a formé plainte contre ledit procès-verbal, reçu le 14 juin 2018. Il a conclu à ce que sa plainte soit considérée comme déposée en temps utile, subsidiairement à l'octroi d'un nouveau délai de plainte de 10 jours, dans la mesure où il avait été empêché d'agir sans sa faute dans le délai.
Il a exposé que le lundi 25 juin 2018 vers 23h30, Me E._, avocate-stagiaire de l'Etude de son conseil, et F._, assistante, s'étaient rendues à un automate " MyPost24 " situé boulevard du Pont-d'Arve 40, à Genève. Après avoir déposé le colis contenant la plainte dans la case sélectionnée, lequel portait le numéro de recommandé xx.xx.xxxxxx.xxxxxxxx (code à barres préalablement disposé sur le colis par les prénommées [cf. lettre du 10 juillet 2018 p. 2; <ref-law>]), et refermé la porte de celle-ci, l'automate n'avait pas confirmé la prise en charge du colis et s'était réinitialisé sans délivrer de quittance. Un témoin pouvait confirmer ce qui précède. Celui-ci avait envoyé un pli selon le même système quelques minutes plus tard et avait reçu une quittance. Le 26 juin 2018 à 00h20, Me E._ et F._ ont adressé un courriel à La Poste afin d'obtenir la confirmation de leur envoi, malgré l'absence de quittance. Le 27 juin 2018 à 9h53, elles ont consulté le " Track&Trace " relatif à leur envoi, sur lequel figure la mention " recherche déclenchée ". Le 5 juillet 2018, la secrétaire de l'Etude informait F._ que La Poste avait indiqué que l'envoi était perdu et qu'une réclamation pouvait être envoyée par courriel.
B._ a conclu à l'irrecevabilité de la plainte, tardive, subsidiairement à son rejet. L'Office a confirmé le non-lieu de séquestre et conclu au rejet de la plainte.
A.d. Par décision du 8 novembre 2018, expédiée le lendemain, la Chambre de surveillance a rejeté la requête de restitution de délai et a déclaré la plainte irrecevable pour cause de tardiveté.
B.
Par acte posté le 23 novembre 2018, A._ exerce un recours en matière civile contre la décision du 8 novembre 2018. Il conclut à son annulation et à sa réforme en ce sens, principalement, qu'il est dit que sa plainte datée du 25 juin 2018 a été formée en temps utile, et, subsidiairement, qu'il est dit que la requête de restitution de délai du 10 juillet 2018 doit être admise. " En tout état ", il sollicite du Tribunal fédéral qu'il " demande " à la Cour de justice d'entrer en matière sur la plainte datée du 25 juillet 2018.
B._ propose le rejet du recours. La Chambre de surveillance s'est référée aux considérants de sa décision. L'Office ne s'est pas déterminé dans le délai imparti à cet effet.

Considérant en droit :
1.
Interjeté dans le délai légal (<ref-law>) par la partie qui a succombé dans ses conclusions prises devant l'autorité précédente (<ref-law>) et dirigé contre une décision finale (<ref-law>) rendue en matière de poursuite pour dettes et de faillite (<ref-law>) par une autorité cantonale de surveillance de dernière (unique) instance (<ref-law>), le recours est en principe recevable, et ce indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF).
2.
2.1. Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.3; <ref-ruling> consid. 2). Cela étant, eu égard à l'exigence de motivation contenue à l'<ref-law>, sous peine d'irrecevabilité, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui pourraient se poser, mais uniquement celles qui sont soulevées devant lui (ATF <ref-ruling> consid. 2 et les références), sauf en présence d'une violation du droit évidente (<ref-ruling> consid. 1.7.1; <ref-ruling> consid. 2; <ref-ruling> consid. 1.6). En outre, le Tribunal fédéral ne connaît de la violation des droits fondamentaux que si de tels griefs ont été invoqués et motivés par le recourant (" principe d'allégation ", <ref-law>), c'est-à-dire s'ils ont été expressément soulevés et exposés de façon claire et détaillée (<ref-ruling> consid. 2.1; <ref-ruling> consid. 2.4).
2.2. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ceux-ci ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>).
3.
La Chambre de surveillance a tout d'abord rappelé les conditions d'une restitution de délai au sens de l'<ref-law>, rappelant ce que pouvait constituer un empêchement non fautif. Elle a ensuite retenu qu'il pouvait en l'espèce être considéré que le plaignant avait été empêché de déposer sa plainte le 25 juin 2018, soit dans les dix jours suivant la réception de la décision querellée, sans faute de sa part. Le dysfonctionnement du service " MyPost 24 ", dont il n'y avait pas lieu de douter, ne pouvait en effet lui être imputé. Cela étant, dès le lendemain, 26 juin 2018, le plaignant n'était plus empêché de déposer sa plainte directement au greffe ni de l'envoyer par la poste. Il lui incombait dès lors, dans le délai de dix jours dès la fin de l'empêchement, de déposer une requête motivée et d'accomplir auprès de l'autorité compétente l'acte juridique omis. En procédant de la sorte le 10 juillet 2018 seulement, le plaignant avait agi tardivement. Peu importe que La Poste ne lui eût confirmé que le 5 juillet 2018 que son envoi était perdu. Dûment représenté par un mandataire qualifié, il appartenait à ce dernier d'agir rapidement, au risque que la plainte parvienne à deux reprises à l'autorité de surveillance. La requête de restitution de délai devait donc être rejetée et la plainte déclarée irrecevable, car tardive.
4.
Le recourant invoque une violation de l'<ref-law>. Il soutient que la Chambre de surveillance a retenu qu'il avait mis dans la " boîte aux lettres ", le 25 juin 2018 vers 23h30, un pli contenant la plainte. Fort de ce constat, elle aurait dû considérer que l'acte de procédure litigieux avait bel et bien été accompli en temps utile. Le dépôt d'un courrier dans une boîte aux lettres constitue en effet une remise à la poste à l'attention du Tribunal au sens de l'<ref-law>. La perte ultérieure du pli n'y changeait rien. L'envoi du 10 juillet 2018 s'apparentait à l'envoi informel d'une copie de la plainte pour permettre à l'autorité saisie de la traiter, comme si cette dernière avait égaré l'original.
4.1. Selon l'<ref-law> - qui correspond matériellement à l'<ref-law> (arrêt 4A_215/2015 2 octobre 2015 consid. 3.1) -, applicable par renvoi de l'<ref-law>, les actes doivent être remis au plus tard le dernier jour du délai soit au tribunal soit à l'attention de ce dernier, à la poste suisse ou à une représentation diplomatique ou consulaire suisse. Le délai est sauvegardé si l'acte est remis le dernier jour du délai à minuit (<ref-ruling> consid. 2.2 et les références). En cas de doute, la preuve du respect du délai, et donc d'une telle remise, doit être apportée par celui qui soutient avoir agi en temps utile au degré de la certitude et non simplement au degré de la vraisemblance prépondérante; elle résulte en général de preuves " préconstituées " (sceau postal, récépissé d'envoi recommandé ou encore accusé de réception en cas de dépôt pendant les heures de bureau; arrêts 8C_696/2018 du 7 novembre 2018 consid. 3.3; 1B_220/2018 du 11 septembre 2018 consid. 4; TAPPY, in Commentaire romand, CPC, 2ème éd. 2019, n° 8 ad <ref-law>); la date d'affranchissement postal ou le code à barres pour lettres avec justificatif de distribution imprimés au moyen d'une machine privée ne constituent en revanche pas la preuve de la remise de l'envoi à la poste (cf. JEAN-MAURICE FRÉSARD, in Commentaire de la LTF, 2ème éd. 2014, n° 33 ad <ref-law> et l'arrêt cité). D'autres modes de preuves sont toutefois possibles, en particulier l'attestation de la date de l'envoi par un ou plusieurs témoins mentionnés sur l'enveloppe (<ref-ruling> consid. 2.2 et les références; arrêts 2C_404/2011 du 21 novembre 2011 consid. 2.3, in RSPC 2012 p. 113; 5A_267/2008 du 16 octobre 2008 consid 3.2, in RSPC 2009 p. 34 et 153); la présence de signatures sur l'enveloppe n'est pas, en soi, un moyen de preuve du dépôt en temps utile, la preuve résidant dans le témoignage du ou des signataires; il incombe dès lors à l'intéressé d'offrir cette preuve dans un délai adapté aux circonstances (" innert nützlicher Frist "), en indiquant l'identité et l'adresse du ou des témoins (arrêt 8C_696/2018 précité consid. 3.3).
4.2. Depuis l'été 2015, La Poste a procédé à l'installation, dans des gares ainsi que dans les principaux centres urbains, d'automates postaux dénommés " MyPost 24 " (cf. www.post.ch/Mypost24). Il s'agit d'offices postaux automatisés, actifs 24/24h, permettant notamment de recevoir et d'expédier des colis et autres envois en suivi. Après dépôt du pli dans une case, l'automate délivre à l'expéditeur une quittance imprimée comportant un numéro de suivi et l'indication de l'heure de la date du dépôt (cf. STÉPHANE GRODECKI/ROMAIN JORDAN, Code annoté de procédure administrative genevoise, 2017, n° 308 ad art. 17 LPA/GE p. 86; ROMAIN JORDAN, Le respect des délais pour l'avocat, in Revue de l'avocat 2016 p. 206 ss, 210).
A l'instar d'une boîte postale (cf. <ref-ruling> consid. 2.2; arrêt 8C_696/2018 précité consid. 3.3 et les références), il y a lieu d'assimiler l'automate " MyPost 24 " à un bureau de poste suisse au sens notamment de l'<ref-law>, à charge, le cas échéant, pour l'expéditeur de prouver que le délai a été observé (cf. supra consid. 4.1).
4.3. Contrairement à ce qu'affirme le recourant, il ne résulte pas de la décision querellée que les juges précédents auraient tenu pour établi que le pli contenant la plainte a été remis à la poste le 25 juin 2018 vers 23h30. En retenant que le recourant avait été empêché sans sa faute de déposer sa plainte le 25 juin 2018 en raison du dysfonctionnement de l'automate " MyPost 24 ", ils ont au contraire constaté que le recourant était dans l'impossibilité de fournir la preuve " préconstituée " (i.c. quittance) attestant de la date d'envoi du pli litigieux. Au demeurant, le recourant ne peut rien tirer de l'état de fait de la décision entreprise, dès lors qu'il ne fait que reproduire ses propres allégations en lien avec le processus de remise du pli en cause à l'automate " MyPost 24 ". Dans ces conditions, il incombait au recourant de prouver qu'il avait bien déposé celui-ci le 25 juin 2018 avant minuit. A cet égard, ce dernier ne prétend pas, à juste titre, que le numéro de recommandé résultant du code à barres préalablement apposé sur le pli lui permettrait d'apporter cette preuve. Il est par ailleurs constant que l'automate " MyPost 24 " a dysfonctionné en tant qu'il n'a remis aucune quittance. La preuve de l'observation du délai ne pouvait dès lors être fournie que par un autre moyen. Le recourant en était bien conscient puisqu'il a offert de prouver ses allégations par le biais des déclarations d'un témoin, dont il a donné à la Chambre de surveillance l'identité et l'adresse. Force est toutefois de constater qu'en attendant le résultat de ses démarches auprès de La Poste pour ce faire, il n'a pas agi dans un délai adapté aux circonstances. Dès lors que le 25 juin 2018, il savait que, hormis un témoignage, il ne disposait d'aucune preuve de la date de l'envoi de sa plainte, l'on pouvait raisonnablement attendre du recourant que, dès le lendemain, il s'adresse à la Chambre de surveillance dans le sens susvisé.
Il suit de là que le grief de violation de l'<ref-law> est dénué de fondement et qu'il doit être rejeté.
5.
Le recourant se plaint d'une violation de l'<ref-law>. Citant un commentateur de l'<ref-law>, il soutient que, dans les circonstances telles que celles de l'espèce, le dies a quo du délai pour requérir la restitution et accomplir l'acte omis court à partir du moment où le " recourant " a su, ou devait savoir, qu'il a été empêché. Or, il estime qu'au moment de la remise du pli dans la case de l'automate, il n'avait aucune raison de douter que le pli avait bien été pris en charge et qu'il serait acheminé à l'autorité destinataire. Le fait que le système remettant un accusé de réception avait dysfonctionné n'affectait que les moyens dont il disposait pour apporter la preuve du dépôt en temps utile. Il n'avait au demeurant pas à s'en inquiéter, puisqu'il disposait d'un témoin externe, ce qui était suffisant. Ce n'était qu'au moment où il avait reçu, le 5 juillet 2018, l'avis de La Poste qu'il avait su que l'envoi avait été perdu. C'était donc à partir de ce moment-là que courait le délai pour requérir la restitution et accomplir l'acte omis; en faisant ces deux actes de procédure le 10 juillet 2018, il avait donc agi en temps utile. Dans une argumentation subsidiaire, le recourant soutient qu'il faudrait en tous les cas tenir compte des délais d'acheminement du courrier pour que l'on puisse lui opposer qu'à un certain moment, il devait partir du principe que le pli ne parviendrait plus à l'autorité de surveillance, moment qu'il situe au plus tôt au 2 juillet 2018.
5.1. Aux termes de l'<ref-law>, qui constitue une lex specialis par rapport à l'<ref-law> (JOLANTA KREN KOSTKIEWICZ, Schuldbetreibungs- & Konkursrecht, 3ème éd. 2018, n° 253 p. 68), quiconque a été empêché sans sa faute d'agir dans le délai fixé peut demander à l'autorité de surveillance ou à l'autorité judiciaire compétente qu'elle lui restitue ce délai. L'intéressé doit, à compter de la fin de l'empêchement, déposer une requête motivée dans un délai égal au délai échu et accomplir auprès de l'autorité compétente l'acte juridique omis.
La restitution de délai ne peut être accordée que si l'empêchement n'est entaché d'aucune faute. Entrent en ligne de compte non seulement l'impossibilité objective ou la force majeure, mais aussi l'impossibilité due à des circonstances personnelles ou à une erreur excusable. Ces circonstances doivent être appréciées objectivement en ce sens qu'est non fautive toute circonstance qui aurait empêché un intéressé, respectivement son représentant, consciencieux d'agir dans le délai fixé (arrêts 5A_149/2013 du 10 juin 2013 consid. 5.1.1 et les références citées; 5A_896/2012 du 10 janvier 2013 consid. 3.2; 5A_30/2010 du 23 mars 2010 consid. 4.1 et les références citées; GILLIÉRON, Commentaire de la loi fédérale sur la poursuite pour dettes et la faillite, t. I, 1999, n° 40 ad <ref-law>). La faute du représentant est assimilée à la faute de l'intéressé conformément aux règles sur la représentation directe (GILLIÉRON, op. cit., n° 42 ad <ref-law>). De même, s'agissant des auxiliaires, l'application des motifs exonérant la responsabilité de l'employeur selon l'<ref-law> est exclue (arrêts 5A_30/2010 précité; 2P.264/2003 du 29 octobre 2003 consid. 2.1 et les références).
Le dies a quo du délai pour déposer la requête motivée de restitution est celui où cesse l'empêchement et non celui où l'intéressé reçoit la décision d'irrecevabilité de l'acte de procédure accompli après l'expiration du délai initial. Celui qui devait sauvegarder un délai légal ou imparti par un organe de l'exécution forcée ou un juge dans l'exécution des tâches que leur attribue la loi et qui a été empêché de l'accomplir, ne doit donc pas attendre que cet acte ait été déclaré irrecevable pour demander la restitution du délai qui n'a pas été observé; au contraire, il doit, dans le délai qui court dès la cessation de l'empêchement, demander la restitution du délai qui n'a pas été observé et, simultanément, accomplir l'acte de procédure omis (arrêts 5A_801/2013 du 21 janvier 2014 consid. 3.3, in BlSchK 2015 p. 61; 5A_846/2012 du 4 novembre 2013 consid. 7.3, in SJ 2014 I 109; cf. ég. arrêt 5A_673/2017 du 22 mars 2018 consid. 2.3.1).
5.2. En l'espèce, il n'est pas contesté qu'en date du 25 juin 2018, le recourant pouvait justifier d'un empêchement non fautif en raison du dysfonctionnement de l'automate " MyPost24 ". Reste donc à déterminer si cet empêchement a pu perdurer au-delà de cette date, notamment, comme le soutient le recourant, jusqu'au jour où La Poste a annoncé la perte du pli (5 juillet 2018).
Le recourant ne fait valoir aucun motif convaincant qui expliquerait pourquoi il a été capable, dès le 26 juin 2018, d'effectuer des démarches auprès de La Poste, mais non de solliciter, en parallèle, la restitution du délai auprès de l'autorité de surveillance. En raison du dysfonctionnement avéré de l'automate - qui non seulement n'avait pas généré de quittance mais s'était de surcroît, selon les dires mêmes du recourant, réinitialisé -, il ne pouvait raisonnablement partir du principe que le pli allait néanmoins être acheminé comme s'il avait été posté dans une boîte aux lettres ordinaire. Fallait-il le présumer, que le recourant, assisté d'un mandataire professionnel, n'était pas sans ignorer que, faute de quittance, il devrait prouver la date d'envoi du pli par un autre moyen, soit en l'occurrence par le biais des déclarations du témoin présent le 25 juin 2018 et dont il connaissait tant l'identité que l'adresse. Il n'est partant pas excusable de ne pas avoir saisi le premier moment utile, à savoir le 26 juin 2018, pour agir devant l'autorité de surveillance et, notamment, requérir l'audition dudit témoin. C'est donc à bon droit que la Chambre de surveillance a jugé qu'il aurait appartenu à l'intéressé de déposer une requête motivée dès cette date, dans un délai de dix jours, égal au délai échu, et d'accomplir l'acte juridique omis, ce qu'il a en l'occurrence fait tardivement.
Infondé, le moyen doit être rejeté.
6.
En définitive, le recours doit être rejeté. A titre de partie qui succombe, son auteur doit acquitter l'émolument à percevoir par le Tribunal fédéral (<ref-law>) et les dépens auxquels l'autre partie peut prétendre (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3.
Une indemnité de 3'500 fr., à payer à l'intimé à titre de dépens, est mise à charge du recourant.
4.
Le présent arrêt est communiqué aux parties, à l'Office des poursuites de Genève et à la Chambre de surveillance des Offices des poursuites et faillites de la Cour de justice du canton de Genève.
Lausanne, le 5 février 2019
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : Herrmann
La Greffière : Hildbrand