FWIW, UPlay (or whatever it's called this week) has an exclusive bundle of the entire Settlers History Edition series, complete with some addons that were never released in English elsewhere, that goes down to about £12 when it's on sale. Obviously that's DRMed up the wazoo, though, but it's a cheap way to get the whole franchise.

Ditto.

I would go for Settlers II Gold. And if you like it you should get The Settlers 2: 10th Anniversary too.

If you like the "new" Settlers 2 you should have a look at "Die Siedler: Aufbruch der Kulturen". But keep in mind that this one is German only. Perhaps there is a fan patch for other languages.

The Settlers 2 Gold. The original has some hand-painting graphic style that the others lack.