As already suggested - Chess. But to make it really kick some arse, implement it with yahoo games server or server of it's own, where one can play over the wireless with other people. The data transfer in this game is minimal and yet playing against smbd else and not AI makes the big difference. EInk screen is not an issue too, as there's no rush...
|