I build barracks as soon as I can. I know that they cost gold to maintain, but I just hate building troops that are not veteran.
Early in the game, once I've planted a city, I build a defender (which will of course be a regular unit). If I'm not going to use that city to produce a settler, I'll usually build a temple and then a barracks, especially if said city is on the border with a less-than-friendly neighbor. Then I'm able to build veteran units that can be used for attack (or increased defense) against aggressive AI's.
I typically build barracks in my biggest two or three cities as soon as possible from which I will produce virtually all horse-base units and swordsmen. (The only regular swordsmen I generally have will be warriors that were upgraded.)
Maybe it's just me but I feel that I have a slight advantage in the early game by utilizing veteran troops over the AI's typically regular units. And (whether justified or not) I've always felt that regular troops are too vulnerable.
So my preference is to build barracks in key cities as soon as possible, build troops there, and move them to the frontiers. Then the "older" regular units can be moved to the interior of the empire for military police duty in the less-vulnerable cities.
Because of this I almost never build Sun Tzu's Art of War, instead concentrating on other wonders since by the time it's available I will have barracks in most, if not all, of my cities. (Granted Sun Tzu's AoW would be nice--no barracks maintenance--but if I have barracks in most cities and it's a choice between Sun Tzu and some other wonder--especially Sistine Chapel--I'll concentrate on the other wonder instead.)