Try jumping up to emperor. I started playing at king and I was having the same sort of games you're describing. Since I moved up to emperor and again to immortal, I've noticed the AI seems to have larger armies with each successive step up.
Then again, maybe I've been fortunate with this game -- it's possible the the dice have just rolled well. Maybe the conditions of the world I'm playing are pretty ideal too. With a few exceptions, there is quite a lot of good land for each civ and natural borders that seem perfectly placed for each civ to expand within. Also, because there's 10 civs on one continent (19 in the game with 25 CS), it seems that everyone's borders are starting to bump each other at about 6 to 9 cities each. So, there shouldn't be the problem where one civ has access to a huge swath of land and is able to place 25 cities or some crazy amount.
AI seems to be making no real effort to build a substantial military at all.
So, I last posted at turn 125 or so. It's 35 turns later. I completed my military buildings in my 3 military cities (one for melee, one for mounted, and one for naval). Melee city built 1 immortal and 1 swordman; mounted city built 1 chariot archer and 1 horseman; and the naval city built 1 trireme. Result, I've moved from 6/10 military to 3rd largest military. I'd say I pretty much doubled the size of my military and there's still 2 civs on my continent with a larger military.
I'm about settle my 8th city. 2 civs have 9. And I gotta say -- they seem to be picking good spots. In fact, it's been pretty annoying because I've been beat to at least 3 areas that I really wanted for strategic reasons. Not only did the AI beat me to those 3 areas, but they settled on the tile most strategic given their location relative to mine, e.g. on a hill tucked behind a river.....
On the other hand, I've noticed that the Chinese and the Americans have settled in some pretty bad locations, but then again, they're sort of boxed in and they don't really have access to good land without settling behind other nations' lands.