High Top Tevas also have the added bonus of stink accumulation. I love mine, but they get manky after extended use in summer. None of my other footwear do, it annoys me.

As with Ian and others suggestions - I'd get a pair of fell shoes. But, they won't have any sort of midfoot stability like a riding shoe will. Long pins may also ... dig in a bit. So run shorter pins.