This is one of the best games for the Linux console. You play against the computer on a map made of various islands.
Understanding the commands is a little tricky at the beginning; you have to understand the difference between three different modes, but once you get accustomed to it, it becomes quite addictive. Games last several hours.
The game seems to be available as a package called empire or as a source code called vms-empire (which can be found here).