I've only recently moved up to Regent and I'm on my third game now. I won the first two games (well, I quit when it was obvious I was going to win, which isn't technically a win....) by following a post in the Strategy Articles on early expansion. Basically, in my capitol city and in about my first 6 or 8 cities which are founded close to the capitol (i.e. low corruption), I have the following build queue :
Capitol : warrior (send scouting), spearman (fortify), barracks (but switch to granary when I discover Pottery, the first tech I research), settler, settler, temple, worker, settler.
Close Cities : warrior (fortify), granary, settler, spearman (fortify, then send warrior scouting if needed), settler, temple, worker, settler
If you play an expansionist civ, use the same build order in the Capitol as the close cities, since you'll already have Pottery.
While my initial expansion is a little slower, because my first settler isn't built right away, once I get the granaries in the cities, the rate at which settlers are being pumped out is incredible. In some cities with good food production (like a wheat square), you can often produce settler after settler after settler.
Now, once I start building cities that start to suffer from corruption, my build order changes to Spearman then temple. My outlying cities will never be settler farms. Circumstances in each city will determine what I do after my temple. It's usually another spearman if other civs are close by, or a barracks then spearman if I've got some time. Also, at this point I'm often producing extra spearmen in my early cities which I'm sending straight to the newer cities. I'll build a temple first in these outlying cities if a spearmen is en-route.
I've found that the number of military units you're producing early on is enough to keep the AI at bay while you expand. Once you've either run into civs or water everywhere you can expand, or when you reach around 20 cities, I drop the expansion strategy and start churning out defensive units. The AI will eventually get smart enough to attack you if you keep up the expansion for too long, and they'll probably steam roller over you. At the point when you stop expanding, you're militarily weaker than neighbouring civs, and you'll be behind in the tech race if you haven't been busy trading techs. However, you'll be in the lead culturally (because of all your temples), you'll own the most amount of land, and have the largest city base. These three things should be enough to put you over the top in the centuries to come. Once you've foritifed your cities with defensive units, start cranking out fast moving attach units and go after the tastiest looking civ nearby.
I think this strategy might be best suited for the English (Expansionist and Commercial). The Expansionist trait gives you Pottery right off the bat, so you can build granaries from day one. The scout will help you find the right places to found your cities, and will help you in the tech race by possibly finding techs in goody huts. The commerical attribute will lower corruption slightly, possibly allowing you to use the above mentioned build queue in more cities. I've only tried this with the Egyptians and the Chinese, since I find it very hard to not choose an Industrious civ. Also, choosing a civ with an early UU might not be a good idea. You don't start building offensive until the early middle ages. I found the Chinese a good fit, since the fast moving Rider became available at roughly the time I wanted to start kicking some ass.
Anyway, that's my two cents worth. Expand, expand, fority, attack. Others will tell you to build about six cities and then start attacking, and that may be what you need on higher levels, but on Regent, since I'm a builder at heart, I really enjoy this strategy. Also, I'm by no means an expert, having finished two game on Regent.
