I am a REXer by nature. It seems as though the current AI (G&K) punishes you pretty harshly from a diplomatic standpoint if you settle more than the "average" number of AI cities. In some games, I have noticed the diplo hit for "we think you are overexpanding" has a very quick trigger, sometimes as soon as dropping the fourth city. My guess (and I am not a code-delver) is that it is somehow tied to the median number of cities per empire, and when you get over that by a significant margin, everyone (even Friends) starts to denounce you. So I now believe (at least until diplo is changed in a patch) that REXing should be considered a warmonger strategy. The days of going peacefully wide-then-tall are over, at least for now.
This has substantial ramifications for policies, beliefs, and UAs that are granted on a per-city basis and presents a pretty convincing case that Tradition is just as valid a choice as Liberty, even before considering the changes to those policy trees in G&K.
Back on topic, I build walls when I have time, but often like to have 400 gold on hand (standard speed) to rush-buy walls. Walls, especially with Oligarchy and a garrison unit, make a city almost unassailable by the AI unless they are 2 tech generations ahead of you. Also, puppet cities often build walls on their own. To me this makes Professional Army a doubly worthwhile policy for anyone waging offensive war -- bonus happiness for walls plus cheaper unit upgrades.
As far as defensive units are concerned, beyond ranged units it is useful to have a meat shield or two to clog up the defensive terrain and deny the AI access. Mounted units are also handy to exploit an enemy's rear or flank, but this is very map-dependent. When executed well, a horseman counterattack is simply awesome, and then you are in prime position to pillage your attacker's cities, steal his workers, and bring up your ranged/siege units to start attacking him in earnest.
