There was "the perfect general" which was a simplistic hex-based wargame that played well against the AI, and was even better when I hooked up my Atari ST to my friend's Amiga via a serial cable. Wiki says that was 1991 my how time flies!.
Apparently still available -
http://killerbeesoftware.com/kbsgames/pgnew/
Something to download and try again!