A implementação de um Map é de fato diferente da de um Object. Tem algumas diferenças simples de se notar degugando, por exemplo: Se você percorrer os atributos de um Map, eles são iterados na ordem de insersão; já se você percorrer os atributos de um Object com um Object.entries(), a ordem de insersão não necessariamente é respeitada.

Não investiguei então não sei dizer com precisão em que se diferencia a performance de um Map e um Object, mas eu também acredito que um Map tenha mais vantagens nesse quesito. Embora a complexidade permaneça O(1) igual o colega falou, imagino que possam ocorrer menos colisões nas funções de hash ou coisas do tipo.

Pra mim a única vantagem do Object é a sintaxe pra diversas manipulações que você não consegue fazer com tão poucas linhas num Map.