I've never used Chef, with or without Vagrant, but I have used Puppet.
It's generally better to have a shell script install your provisioning tool, or use a box that already has it installed, than depending on Vagrant to do anything for you.
I liked Ansible a lot; during our evaluation I had a single Ansible file provisioning a sample dev setup in around 50 lines. We need to support windows servers primarily, much to my objection, so the 'blessing' of the machine to automate Ansible on windows required a manual step at the time, which wasn't acceptable for our use case. We ended up picking chef, both for it's more agnostic approach to OS's, but also it's much more developer friendly, regardless of it's overly verbose generators, git repository litter, and quirks that still have me scratching my head.
Otherwise, another option is to either use prebuilt Vagrant boxes with your CM tool already installed, or build your own using Packer.