I've got a bunch of them, and my favorite is Dec Hogans Modern Speycasting DVD. It may not be the best in terms of taking a novice from step 1 to 2 to 3 to......, but just watching it conveys the sweet ease of casting I aspire to and Hogan breaks it down enough to get the basics of his mechanics across. Henrik Mortensens comes in a close second and is actually more informative in a technical sense. I guess just watching a great caster like Hogan do his thing is more inspiring than watching the "Put peg A into slot B" type videos and if you already have the basics down it will challenge you to raise the bar. These are both tapes for anglers who have an understanding of the basics and are aimed at training intermediate skill levels.
However, that said, if I was to hand an instructional tape over to a newbie it would be the Hazels tape because it does lay out all the basics so well, and I'd say viewing the Rio International tape would be a must after that. Lesson 2 if you will.