You might try a safety boot with a non-slip sole from these guys:
http://www.shoesforcrews.com/sfc3/index....partnumber=8280They apparently are pretty confident in the technology, somewhere on the site it mentioned that they have a "slip and fall" warrantee where they'll reimburse up to $5000 for any workers comp claim because you slipped in their boot.