How do I attach a wooden post to existing concrete steps?
I think you just about answered your own question.  

I would attach the posts directly to the sides of the steps, with the posts extending down as far as possible.  This will get you more bearing surface between the posts and the steps, and allow for more anchors in the masonry spaced further apart.  This will make all the difference.  I think the sheet metal mounts will always be prone to wobble.   

The expanding sleeve anchors in your question are probably as good as anything for this, make sure you use long ones, even with 2x4's.  In perfect concrete with a perfect hole, you wouldn't need that much embedment to secure the wood adequately, but this masonry is questionable compression strength and quality, so I'd go for as much embedment as possible.  The 5/8" x  6" pictured in your question is probably just right, you'll have over 4" of embedment and that should be very strong.    

I might use 2x4 rather than 4x4 posts.  The thicker the wood, the less embedment of the anchor, and the more it will wobble;  this may be hard to picture, but with a 4x4, the lever arm you have between the head of the fastener and the anchoring in the concrete is doubled.  You're not holding up a deck, just a hand rail, 2x4s are adequate.  You could also shorten the lever by countersinking the nut and washer into the 4x4.  

Another way to go would be to double up two 2x4's, with the second 2x4 inside the first, with its butt sitting on the top of the step.  You could get the same effect by rip cutting a half-lap into a 4x4.  This might be the sturdiest of all, since the butt bearing on the top of the step would stiffen things a little more.  

By the way, for future reference - when tapcons break like that, it's usually because there's some dust left in the hole from drilling, you can blow it out with canned air or other method.