Gatorskins are the worst possible choice. I wouldn't even ride them on training rides.

As others have said, GP4000S's are a very good option, with high levels of flat protection (I use them to commute through industrial areas every day) and among the best rolling resistance.

If you'd like to learn about latex tubes and sealant, there are some good threads on here. And lastly, don't listen to your bike store.

---

'It never gets easier, you just get crazier.'