1) What level are you all playing on? It's hard to compare apples with apples. Also, I've noticed that certain civs are more warlike, while others are more research oriented.
2) If you're used to defeating the cheating AI in warlords, then you're going to have to play at a higher level. Emperor in BtS, especially for war-mongerers is more like what you saw in Monarch level in Warlords for warmongering. I would, however, submit that if you aren't a war-mongerer, then you'll find the AI more challenging if you try to go for the other victory conditions.
3) I have never seen a frozen AI...but I do always play with the Aggressive AI turned on.
4) Did you regen the map to get a Great Start? I had a game, where my start position was seriously better than every AI except 2 on a Large Terra Map. This allowed me to get every wonder built, even though there was one Industrious AI, and I was the Dutch, being Financial and Creative.
I have a game going now as the Romans under Augustus Ceasar on Monarch, Terra Map, Large. I did rush Axemen and took out my nearest AI in the first 60 turns...poor sob only had one Bowman vs. my 4 axeman stack
However, my next competitor, Asoka, was too far to make it financially viable to take him out early on. It is now 1100AD and we have been locked in a war, involving coastal battles between Triremes, and now Caravels, and huge land battles, involving stacks of War Elephants, Chariots, Horse Archers, Longbowmen, Crossbowmen, Praetorians, Macemen, Axemen, Catapults, and Trebuchets.
Rather than just moving my SOD from city to city, I have to deal with his reinforcements and his troops intercepting my reinforcements, and stacks that attempt to retake lost cities...
An earlier poster stated that he thought the AI was still cheating, due to what his espionage abilities were revealing. I can tell you that with 6 good cities, 3 of which are in real nice locations, I am churning out 3-5 units every other turn. India has more cities. In the North, he has his production cities, and in the South (bordering my empire) he has his commerce cities. I admit that I tweaked Rome a little, but that was it.
What I'm saying is that the AI isn't cheating production wise, but that he is micro-managing like a pro...at least in this case. He's at war for his survival, so he is switching to hammer focus, then using slavery to wip a unit, then switching to food to rebuild the lost pop, then hammer, then wip and rince and repeat...all all all of his cities are doing this. Sounds like a good strategy to me. Unfortunately, he will wip his people to death to save his cities. I have seen the AI wip down to a size 2 city from size 12 over a long war to pump out units. (Is that a bug??? Would you do that? Facing the demise of your civilization, what would you do, other than quit the game and start over?)
On the flip side, I've had wars on other games, where the AI knew it was outmatched, and would fall back to defend a few cities. I have also been surprised to find the AI attack my lands behind my armies via routes it had with other civs via open borders agreements.
I even had one experience, where the AI dumped all of its financial resources into espionage points against me in hopes of stealing my tech.