Widelands

Naturally, I tried the Fedora Games Live DVD (is easier than downloading all your games to your Fedora desktop, try them and remove) and one of the few I could see me playing is Widelands.
It is basically a reimplementation of the classic Settlers II which I used to like and play about 10 years ago, but with a slightly worse interface, a bit more buggy and with less maps. However, it has the same look and feel and some additional benefits: larger screen resolutions, network play, freedom...