I once went for early religions, not for the shrine, but for the free culture for border pops. Turned out religious expansion isn't as reliable as I thought. As for shrines, if you settle a great priest, that's 5 gold regardless of religion. Early game, you have to get lucky for a shrine to do much better. Oh, and the happiness bonus at your level isn't that high. Also sometimes people hate you.
My point being religion, while nice for some things (culture, happiness), delays you in worker tech for a long time. It's not good to get for side benefits, often early religion is a long term strategy, which accepts the sacrifice of growth early and in the middle (to build missionaries).
People are covering a lot of management issues, so let me delve into diplomacy. Once I discover most of the people on my continent, I open the diplomacy screen, look at the relations web. First check to see if there's one person that everyone hates. Treat him like a pariah (no open borders). Then look for cliques of friends, often religious of warmonger blocks. Now think about everyones score/land relative to you, who you want to take out first, and then choose your friend(s). This is often not a simple problem, I will stop and think about it, sometimes even delay the game half a day or so, because this diplomacy (and war plans) basically determine my long term expansion strategy.
Convert to his religion if you can, do not adopt any other religion, and if you have a spare resource, consider gifting him it. His enemies are not your friends.
Try to goad some infighting, but hope that nobody gets too strong. That slows them down. Tech trading, try to trade with as many not pariahs as you can to multiply your tech benefit. If you have a tech lead, ration out tech trades until other people are on the verge of getting it themselves (check tech diplomacy frequently), then give it to everyone in a clique, even for gold or just diplomatic status.
This way, you minimize AIs trading with each other, reducing the mutual benefit. If you trade 5 times, and they only trade with you, your techs are worth 6x and there's is only 2x.
And tech smartly, you can trade for iron working, mathematics, currency, calendar, feudalism.