In a nutshell, a virtual dedicated server is a server divided up into multiple partitions, and for the most part, each behaving like it's own server, except that the resources are shared.
And a straight dedicated server is as it implies, a box all to yourself, giving you a little more flexibility if you need it.