Way back when, when I was a steppin' foo....about 20 year ago, I had the best step shoes in the world! They were Ryka's. I don't know if they make solely a step shoe now. But they were terrific!
I use cross training shoes for stepping. I would go to a big sports store like dicks or sports authority, they usually have many brands and styles separtated out by type- walkers runners etc... Go try on different brands and compare comfort. I like cross trainers because I feel like they have more support for the side to side moves (less ankle roll for me). The soles are not as flexible as runners, which I also have in my closet for those times I get a little crazy and want to jog! The right shoe is very important though....Don't be afraid to spend a little money if you find one you really like. I end up getting two pairs sometimes.
I love my Asics Gel Upshots. Nice & comfy with great support. If you want to try several shoes, but don't have access to local stores, try Zappo's. They have free shipping both ways. That way you can try several different pairs, then ship back what doesn't work for you.
I do, too. I think they offer good support for some of the high impact moves that can occur with stepping as well as the pivots and stops. I used to wear Reeboks, but lately I've preferred Nike crosstrainers. The soles are nice and springy.