MLP, first of all, try and lace your shoes opposite as usual, kinda. Start with the first loop on the underside and lace away from there. Higher up you can revert back to normal lacing, but the bottom can be reversed to get rid of the problem.

I've had pretty good luck with Puma Speed Cat's, although I usually ride clipless, on my other bike I like those shoes over the other pairs I have. They're pretty low profile, and have really tough rubber on the bottom, albeit somewhat thin.