If one was to describe the gods at that time, they were "like humans, often with the superpowers, but primarily different from the humans by being immortal."(1) That's it. You don't have to completely negate the existence of such entities to claim that Zeus doesn't cause the thunder, or that there are natural laws which fully determine some phenomena. So the "natural philosophers" could search for such laws, negating the particular role of "the gods" but still not having to explicitly declare their complete non-existence.
1) And if you read the Old Testament, you'll find that beautiful scene that reflect the understanding of these times, where "the God" (as we understand him today) makes a visit to the guy, enters his house, sits with him, talks with him, eats with him... Fully comparable to what the gods do in the Iliad, for example. Not to mention that in the Old Testament the "sacrifices" were necessary, even "the God" was regularly "hungry" for the meat of the animals used to feed the "mortal" people. Again just like the gods in the Iliad.
Christianity is a mixed bag. Popular christian imagination is still filled with miracles and supernatural beings acting on human life. On the other hand, many christians don't hold such views and have a much more deflationary account of divinity. But when I think of early christianity, I think of visions of angels, and curse tablets.
Nothing is known for sure what Plato really thought, specially when it comes to his unwritten doctrines. But his dialogues often put a strong emphasis on piety, and he also makes references to magical practice (think Charmides' charm). He's also been heaped by ancient interpreters with groups strongly associated with mystic practices, namely the Pythagoreans and the Eleatics. Neoplatonists, on the other hand, were associated with Julian I's attempt at revitalizing traditional roman religion and with ritual magic (i.e. theurgy), despite their adherence to the idea of a highly impersonal deity.
None of these guys (Christians, Neoplatonists) were quite free from the traditional practices of their times.