First you must discover "Writing".
Then you double-click on the little star next to your capital and chose the civs you wish to make an embassy with. First you must of course have met them.
The computer does expand fast. But not any faster than you can unless you're playing at the higher half of the difficulties. So if you want an explanation, I'd say: good AI programming

At higher difficulties, the computer does get free units and settlers when you start. (As well as a few other benefits.)
About losing with cavalry vs. spearmen... well the most likely thing is that you're attacking them when they have a big bonus to their defense.
Fortified = +25%
In walls or a city (I believe size 7-12) = +50%
In metropolis (Believe size 13+) = +100%
Attacking across river = +25%
From terrain = +10%, +25%, +50% (hills) or +100% (mountain)
Fort = +50%
All these add up and if you're not careful, you may be at a disadvantage even if your attack strength seems larger than the defense strength. Also, regular/veteran/elite status makes a big difference. Building barracks are generally a very good idea.