there are a huge amount of factors, and since i haven't done much in terms of Ai, i couldn't tell u exactly which types of games are hardest.

RTS (Real-Time Strategy) comes to mind -- pathfinding isn't usually too hard as there are a couple of standards out there, but i guess having the computer-controlled players think realistically like a human and develop good battle-strategies would be difficult to program.

FPS (First-Person Shooter) -- it depends what you're making; a serious-sam type game wouldn't have particularly tricky Ai, but a squad-based realistic shooter or something else with computer-controlled allies needs to have really good Ai to avoid frustration and maintain the illusion of intelligence.

Driving Game -- particularly when you have someone chasing someone else, sounds difficult. the pathfinding would be made more difficult as you have to take into account the physical limitations of each car. you don't want Ai players sliding or over-turning as if they've never driven that specific car before, but they need the same limitations as any human player driving that car.

those are my three favourite types of games, put in order of what i think would be most difficult to least difficult. i could be completely wrong but i haven't thought enough about other genres to make any guesses at the moment.

julz