Eu usaria o Ubuntu (ou qualquer um de seus derivados como o Kubuntu), pois ele oferece uma enorme comunidade (por exemplo, no link ou na parte askubuntu da rede de pilha) que é realmente útil. Além disso, muitos posts, etc., lidam com o Ubuntu. Como você é novo no Linux, isso é o que você deve procurar.
Por outro lado, o Linux Mint é baseado no Ubuntu, e muitos posts sobre o Ubuntu provavelmente permanecem válidos.
A pergunta sobre a VM: O Oracle VM VirtualBox é provavelmente uma boa escolha, já que é fácil de usar. Apenas não se esqueça de instalar as adições de convidados ( link ).
Você deve ser mais específico sobre a parte "Linux programming". Muitas pessoas pensam em programação C (ou C ++) de baixo nível ao ler esse termo.