Good Old Games has a few classic chess games at budget prices. Battle Chess was always a favorite of mine when I was a kid. Old graphics, but funny. I'm not sure how good the AI is, since I haven't played it in about 15+ years. It's only $6 though.

I also remember that the Chessmaster series was pretty decent. GOG has Chessmaster 9000 for sale for $10. I never played that one, but it's a lot more modern than Battle Chess, it looks decent, and the entire series has a reputation of being very advanced. I doubt you'd be able to beat it on its toughest levels.