On what difficulty do I have to play for the AI to be challenging?

[gunter]

I agree, I think king is a pretty solid difficulty if you just want to play, build a civ and not worry about exactly how you win.

EDIT: As for people saying they don't like the computer "cheating"...it's the computer. It has to cheat. What is wrong with that? It get's an unfair advantage because you are cheating and getting a ridiculously unfair advantage just by being human.

There are different ways of cheating, the smart one and the pathetic one.

It depends on which one the AI adopts. On middle levels it adopts the first one, on higher difficulty levels it adopts the second one.