Primeiro, você pode (muito provavelmente) usar o DNS do seu registrador.
Ainda não vi um registar que permitisse comprar um domínio, mas não oferecesse hospedagem DNS gratuita. Se você quer a solução menos complicada possível, é mais provável que isso ocorra.
Em segundo lugar, você pode usar um serviço de hospedagem DNS gratuito (ou pago).
Apenas uma pesquisa simples por "hospedagem DNS gratuita" gerou muitos resultados. Se você confia / gosta dessas opções melhor do que a opção DNS do registar (ou o seu registrador não oferece hospedagem DNS), use um deles. Opções de hospedagem de DNS pagas também estão prontamente disponíveis.
Finalmente, você pode hospedar seu próprio servidor DNS.
Você tem um VPS, portanto, sempre pode hospedar seu próprio servidor DNS. Esta é, pessoalmente, a minha opção favorita, pois lhe dá controle total sobre os servidores DNS. Além disso, você afirmou que gosta de código aberto, e a maioria dos servidores DNS é de código aberto. Se você quiser ajuda com isso, eu tenho experiência em configurar o bind9 e estaria mais do que disposto a ajudar, então apenas comente abaixo e eu ajudarei.
Para responder à sua pergunta sobre qual seria a diferença, em geral, a hospedagem de DNS paga pode oferecer servidores melhores e mais, para que seu DNS seja mais tolerante a falhas e resiliente a ataques DoS. É claro que, se você hospedar seu próprio DNS, a estabilidade será determinada pelo quão poderosos são seus servidores. No entanto, como você está servindo apenas um nome de domínio, você precisa de muito menos energia do que os hosters de DNS que enviam toneladas de nomes de domínio (venho hospedando meu próprio DNS em dois VPS de 1 GB RAM de um só núcleo há muito tempo e eles funciona perfeitamente).