Widelands is an open source and free real time strategy game inspired by Settlers I and II. The game is quite popular, addictive and is under heavy development.
Widelands (Build 15) is already available in Ubuntu Software Center but a new version has been released two weeks back – Build 16, which you can install from PPA.
Changes in Build 16
A new scripting engine that allows for complex scenarios
A new watch-me-do tutorial and a new scenario for the Atlanteans
New win conditions for multiplayer games which add variety
Improvements to the user interface in many places
More control over which wares are stored in ware houses