Re: They came!
Eww ... that sounds gnarly. If you still want to wear sandals, both Bite, and Keen make sandals with pretty good toe protection. The Bite Primal is basically a sandal/shoe with loads of ventilation, and a relaxed fit (may be too relaxed for hardcore play -- replacing the bungee lace with regular shoe laces helps). The terrain I play in has cactus, so sandals are a little sketchy (but I still wear them). The Bite Primal works pretty good at giving some protection from splinters and cacti.
With sandals, I always get about a half size larger shoe, so I have about a half inch [of bumper] in front of my toes.