Notei que quando coloquei o dnsmasq o Firefox passou a demorar mais para resolver nomes, o que não faz sentido nenhum pra mim.
Depois habilitar logs no dnsmasq descobri onde estava o problema.
O Firefox tenta resolver o nome pra ipv6 (fazendo uma consulta por um AAAA). Só depois do timeout dessa consulta que ele tentava com ipv4, o que fazia cada consulta demorar muito mais que o aceitável.
Não sei de quem exatamente é a culpa, mas não é nada que não seja contornável via about:config.
Basta trocar o valor de:
network.dns.disableIPv6 para true!
Agora resolução de nomes ultra rápida voltou a ser uma realidade pra mim!