At which level is the AI playing it's best without cheating?
At which difficulty level is the AI playing with the same opportunities as the human player. That is, when does it play it's best and still is not cheating?
Well, the AI is *always* playing at it's best in terms of the AI itself... how it thinks. The only modifications for the difficulty level is the base number of content citizens for you (not sure how this affects the AI), and the production/science bonuses/penalties the AI gets. It gets none at Regent, a 20% penalty at Warlord, a 10% bonus at King (uh, Monarch), and I'm not sure of the others.