Korea and Carthage both start out with an extra units. In the case of Korea, a free worker appears, for Carthage it is a free quinimere (sp??). I've only tested this on Emperor, but it happens consistently. One time my Korean starting warrior vanished and I was left with just the free worker. All of these happened on Communitas map script, Standard, Standard.
edit: just read that Carthage may be starting out with the ship as an intended UA, however, I'd had it spawn inland a couple times, rendering it completely useless.