Try a computer chess game. They usually have good AIs.
All AIs have flaws, and any decent human will eventually spot those flaws and exploit them. My experience is generally that the more complex the game, the weaker the AI, so you could try looking for pretty simple games. It's often best looking for pretty hardcore gaming devs who mostly use internet dealing these days, as they tend to pay more attention to AI as it's more valuable to their customers than mass-market releases.
Some developer names I could suggest - although some do games where you only chuck troops around on a battlefield - with pretty good AIs I've experienced or had recommended are Gary Grigsby, SSG, Panther Games and AGEOD. Frankly, you should beat the AI on any of them as soon as you've got a hang of the game, but hopefully they'll keep you busy for a while.