How to distribute a virtual machine to allow users to try out a dependency-heavy program?
Solution 1:
Personally I'd offer it in Virtualbox and VMWare formats, since Virtualbox is free and VMWare's player is free and well supported and popular.
What do you mean by best way to do it? If you mean offering it to users, you can always create a CD/DVD and offer it free by mail and/or offer it through a CDN or personal website; you don't mention what resources you have available to you. Do you have a website? Is this part of a business? Is it a side hobby?
How big are the resulting images going to be? Do they compress down at all?
Is this likely to be a popular download that can strain your site or tax any transfer limits you have with your provider?
Depending on how savvy your target audience is, you could also offer it via bittorrent to help alleviate the strain on your network (or if you can make agreements with other sites you can divvy it out to them as seed sites). You could even have the images hosted off-site to companies that specialize in hosting large files, so you don't need to worry about content delivery of the large files.
It kind of comes down to a question of what resources you available to you and how savvy your end users are going to be as to how elaborate the requirements you'll impose on the end user just to try out your product. Some may not like having to download separate products to try out your VM. Other sysadmins probably already have VMWare or VMWare player or Virtualbox installed.
Solution 2:
You probably want to be looking into OVF, which is the most likely contender to become an industry standard for virtual appliances. It's predominantly supported by VMware and VirtualBox, which are both platforms you probably want to target; Xen is supported in XenServer and KVM is supported in RHEV, with native support for both underlying hypervisor products still forthcoming.