I've played every version of Settlers since its inception back in the early 90's and love TSOL. One thing I'd love to see which was in Settlers 3 is a bit of wizardry! Love to see the a mage and healer unit: the mage could generate resources, weapons etc., bless the island (zone-wide buffs), turn stone to gold, give soldiers extra strength for adventures - all generated by manna which will involve wine, honey, vineyards, beekeepers. The healer can go along with the troops and heal on site: the more experienced the healer, the more and/or higher levels they can heal.
Also can you guys please put Ali Baba the young woodcutter in the store - even it costs 5000 map fragments to buy.
Cheers!