I just tried a game last night on the C3C mod of Marla Singer's world map, as the Mongols. Amazingly, after discovering Horseback Riding (or the Wheel, whichever one reveals Horse bonus squares), I find that I have NO horses within my borders. None.
What the hell kind of Mongols can I be with no horses?! The only horse nearby was in a Chinese city next door, which was destroyed in the process of liberating it... By this time, I was surrounded by French, Babs, Persians, Celts, and Chinese, of course... With little room to expand, I put a colony on that horse, so now I can be a self-respecting Mongol.
Too bad I probably won't live long enough to actually get to enjoy the horsies.
But yeah, I hate the idea of losing a worker when I colonize something, then my city expands a few turns later. Found that out the hard way. (OK, so I've only been playing Civ 3 for two weeks!)