I used to be completely terrified of trying Step aerobics - it just seemed too complicated and dancey to me. But I kept reading how great of a workout it was, and that you could reap greater benefits doing fairly low impact Step aerobics than high-impact workouts on the floor.
I started with Kari Anderson's "Go: Step for Beginners," followed by Kathy Smith's "Step Workout" and then Cathe's "Basic Step" DVD. These DVDs were PERFECT for me, and I highly recommend them to any beginning stepper as they still have a learning curve to them and are not so simple and boring that you'll lose interest or feel like you're wasting your time. Trust me, once you learn to do a basic step-up / step-down, you WON'T want to keep doing this same move for the next 30 minutes or so - and these workouts thankfully are NOT like that, yet are still easy to learn.
I now have moved on to Cathe's "Bodymax 2" and "Low Max" workouts, and was amazed that I got the choreography down on these about the third time through - and for the first time, I even raised my step height to 8" on LOW MAX the other day.
I admit though, that if I had started with these DVDs I probably would've have gotten so frustrated I would've given up.
Now, I THINK I might be able to try Cathe's IMAX workouts soon, which are supposed to be even a little more complex. ;-)
As for non-step workouts, I've also been eyeing Cathe's "Bootcamp & Muscle Endurance" as well as "Kick Max" as possible next purchases. They both look very intense and fun!