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.

Tem várias diferenças, que estão listadas na documentação. As principais:

Um objeto pode ter propriedades que vêm do protótipo, o que pode acabar dando resultados confusos (principalmente se o protótipo for modificado em outro ponto do código):

// todo objeto terá a propriedade "x"
Object.prototype.x = 1;

const obj = {};
if (obj['x']) { // entra nesse if
    console.log('obj tem x');
}

const map = new Map();
if (map.has('x')) { // não entra nesse if
    console.log('map tem x');
}
// somente se adicionar usando set(), aí passa a ter
map.set('x', 42);
if (map.has('x')) { // entra nesse if
    console.log('agora sim, map tem x');
}

É claro que se acessarmos map.x ou map['x'], a propriedade estará lá. Mas em um Map, você deve usar os métodos has e get para, respectivamente, verificar se a chave existe e obter o valor correspondente.

As chaves de um Map podem ser de quaisquer tipos. Já em um object, pode ser somente string ou Symbol (outros tipos são convertidos para string).

Um Map mantém as chaves na ordem de inserção, e você pode iterar um Map diretamente com for..of:

const map = new Map();
map.set('nome', 'Fulano');
map.set('idade', 42);
// iterar com for..of
for (const [ chave, valor ] of map) {
    console.log(`${chave} = ${valor}`);
}

// em um objeto, precisa usar um método auxiliar
const obj = { nome: 'Fulano', idade: 42 };
for (const [ chave, valor ] of Object.entries(obj)) {
    console.log(`${chave} = ${valor}`);
}

Além disso, a documentação diz que o objeto tem desempenho pior no caso de ter muitas inserções e remoções.

Enfim, não deixe de ler a documentação para todos os detalhes.

Concordo com o uso do Map, acho que a legibilidade do código fica mais legal (geralmente prefiro usar nos meus projetos) e também pelas funções "auxiliares", tipo o has(), mas em termos de performance e consumo de memória acaba por não ter diferença significativa já que tanto no objeto quanto no Map a complexidade é O(1) pra busca e inserção.