I used Avocet Cross K 700x35c tires without slime (hate the stuff) or puncture resistant tubes on my hybrid for two years. The amount of road trash they tolerated was impressive. I never once had a flat. They weren't particularly heavy, only 420g, and cornered pretty well on paved roads covered with sand and gravel. I've even rode several dirt roads and rail trails on them.
I used to go up and down curbs without pinch flats too. After leaving the bike at the family cabin for my parents to use, I find they've consistently let the pressure go down to 40-45 psi every time I visit, and they haven't had a pinch flat either. (although they don't go up and down curbs much
)
The 35c's are a bit tall and narrow in profile, almost as tall as 38c's, so make sure you have sufficient clearance. Consider the 700x32c Cross II K. At 390g, they aren't much heavier than a Gatorskin, more comfortable to ride on, and probably much faster than what you're currently using.
I haven't ridden Gatorskins, but I think of them as more of a light touring tire that is unsuitable for any off road use whatsoever. After all, if you're not going to hit a dirt road every once in a while, then why own a hybrid?
http://www.avocet.com/tirepages/cross_2.html