Beating the AI at Diety in Civ II wasn't always easy either. There are some strategies that are key, like the Super Science City, We Love The Consul Day, the Democracy/Freight combo, and Infinite City Sprawl. There are also Wonders that, it turns out, are pretty much cruicial. I expect it took more than a month or two of playtesting to figure these strategies out. I await the wisdom of my fellow Civ keeners in the Civ III Strategies forum!
There are a lot of Civ players out there chomping at the bit, waiting to prove that they are smarter/more determined than the Firaxis playtesters. I know I plan to spend a 4-day weekend or two giving it my best! Given a favourable starting spot, with room to expand and handy luxuries/stragegic resources, I certainly expect it to be possible to win no matter how much the Comp cheats.
As for "knowing how the AI works"...I already know how the AI works...Like a human, only not as insightful, forethoughtful, creative, or unpredictable! Such is life with AIs, although I am hoping for a big improvement from Civ II.