I'm sure Ribannah and others will have a million good suggestions, but I thought you might appreciate hearing from a fellow beginner.
I play ToT and have won on Deity once (7 civs/raging);
the log of that game is here. You're right: the hyper-aggressive AI makes it very hard. It
can be done, but may require a couple of deviations from the Paulicy. First, you need to get down a city quick; I'd say if you haven't founded by 3750, and done so on a
great site (my win was with a 2-whale 2-silk site, founded in 4000), you should start over. It seems to me that aggressive exploring is also must, for two reasons: you need to find and control chokepoints (as you discovered), and you need contact with as many other civs as possible, but especially the white civ (your "key civ" in OCC). I waited until midgame to explore off my own land mass; I wish I'd done it sooner.
Other things I would suggest: (1) Always declare war when asked to. You can turn around and make peace asap. (2) Play as the Babylonians. Seriously. I find the greens the worst opponents in OCC: The Babs are programmed to play a good perfectionist game, and conduct their own decent race for AC if left alone; the Zulus are just plain insane; and the Japanese are a delightful combination of the two. Take them all out by playing green yourself; and play the Babs, because they're most likely to have starting techs you want.
------------------
Dig trenches, with our men being killed off like flies? There isn't time to dig trenches. We'll have to buy them ready made. Here, run out and get some trenches.
-- Rufus T. Firefly, the original rush-builder