Hi and welcome!
Thanks for providing the information about your goals and interests, etc. It makes providing suggestions much easier knowing this.
I have both Firm BSS systems and as far as being easy on choreography and not needing a full size step (you can buy BSS1 and it comes with a Fanny Lifter that they use for some very basic stepping) these do fit the bill. And I think that they will be effective if you are just starting out. However, my concern would be that you would quickly outgrow these workouts as your fitness progressed. That's what happened for me and now I consider these workouts for my 'light' days when I'm tired, coming off being sick, or need to be careful because of my pesky knees.
Cathe's workouts are wonderful and are in a class by themselves. The weight workouts are simply the best on the market for the at home exerciser. As was stated above, the weight can easily be modified to the beginning level (very light or no weight) and there is definitely room to progress.
I know you said that you wanted workouts that didn't require a step bench. I would encourage you to reconsider. Not only could you do some of Cathe's cardio/weight interval tapes, you could also learn step choreography and the step makes a terrific weight bench! You can get a step and two sets of risers for less than $80 at
www.fitness1st.com.
A great workout that is just strength training (although it does get your heart pumping) for the whole body is Muscle Endurance. It uses a barbell (dumbbells will work fine), dumbbells, a medicine ball (totally optional), and a high step (it is used for step ups, to place a hand on for some bent over exercises to support the back, and to sit on for some exercises). The music is awesome, the whole body gets worked, it doesn't require a full size step, and is VERY effective. This could give you a sense of what Cathe's workouts are like and if you want to invest more money and resources. BTW, if you get the DVD it has Bootcamp, which is intervals of floor aerobics, lower body, upper body, and core work. Actually, now that I think about it, this could be just what you're looking for. I am not recommending Supersets or Push Pull because they include the use of a stability ball and you did not mention if you had and/or wanted to use one.
I think the Pure Strength series would be a great introduction to split body weight training. Here the body is separated into 3 different workouts. The leg and ab tape uses a barbell (once again, dumbbells can work fine), dumbbells, a body bar (optional, it is used for a warm up set of plie squats, for balance on some moves, and for resistance on inner and outer thigh floor work). You can omit the step ups or use a step stool (Rubbermaid has one that is quite sturdy and some use this in place of a high step/fanny lifter). The upper body tapes use much of the same equipment plus a step bench used as a weight bench. While I think you could use the floor just fine, the bench does allow for a little better range of motion. If you like this series, then you could progress to Slow and Heavy or the Pyramids, both fabulous and with their individual selling points.
So, in summary, the Firm systems can get you started and I suspect they won't take you very far. Do consider getting a full size step. If you're not wanting to do that, start with Muscle Endurance and if possible, get the DVD with Bootcamp as the other workout. If you're wanting a split series weight routine, start with Pure Strength and just understand that without a bench some of the range of motion will be decreased.
Good luck!