I voted for the elliptical, too. As Carole pointed out, many ellipticals have a manual setting as well as several preprogrammed settings. Mine came with an HRM, too.
Fach, I'm not aware of any DVD's for use with cardio machines, but iTrain and Cardio Coach are audible HIIT workouts that you can download for use on your computer or mp3 player (Cardio Coach can be ordered in CD for use with a CD walkman). The iClimbs from iTrain are specifically for use with an elliptical or stair climber. Cardio Coach can be used for any machine and for walking/running. When I want to do a steady state workout on my elliptical, I often use a Cathe DVD with good music or just watch something on TV.