Artifacts do push out some pretty serious belief vibes, and if you happen to like decorating your temple and villages (like I do), you'll probably end up with a few of them lying around without your even knowing. I actually had the creature's toy ball turn into a religious artifact once.
Lightning is pretty good for hostile takeovers, as you can cause a flash of belief with a single split-second casting of it. It does minimal damage, while still giving the full belief package of an entire casting. Fireballs are easier though, since you can fling them outside your influence. Also, take note that villagers just need to see giant things flying overhead, they don't need to get hit by them. It helps keep a few people around for when you finally do take over the place.
Flock of Flying Creatures provides an enormous punch for its cost, and has actually led to a couple towns being converted by a single casting over a crowd of people (more people who see it, more belief generated. Try to target large clusters). The Forest miracle also gives some pretty fancy belief scores (and you only need to make the initial casting, just pull the plug once it's finished so you don't have to pay upkeep), the basic Storm is another crowd pleaser (not to mention the fact that it affects a very large area), and a powered-up Healing spell can give some massive belief scores... The first time you cast it. After that, nobody really cares.
Disciples don't give much, but it's a steady trickle. Plop a few down and focus on another target. They'll either take it for you while you aren't looking, or they'll soften it up for when you do shift your godly gaze over at them. Filling the stockpiles is generally only worth it if they have a HUGE need, and if it's a miracle casting for that extra one-two punch.
Like TGGP?? said, mix it up. Once you've done something, the belief value returned for that action drops straight down. They will eventually forget and be just as amazed by it some time later down the line, but right after a casting? You'd be lucky to get half the original return. A combination of Flock, Storm, Lightning and then Healing can net you some pretty damn huge belief scores... Provided you can pull it off.
Apparently, schizophrenic gods are more believable. Who would'a thunk it?