I am a huge Settlers fan. I agree that there is certainly skill involved. With the group I usually play with, I'd say I tend to win 60-65% of our games and if I don't win then it is usually one other guy.
I think the game is much more interesting with Cities and Knights. The commodities add a lot more depth to initial placements and which Cities to upgrade. Barbarians are always a factor to consider (I've won several games where my friends neglected to have the resources to build and activate knights, crippling them early). While I think I have intuitively figured out most of the strategy in the base game*, I am sure there are lots of things I could still learn for C+K:
- relative strengths of the three sets of progress cards (I favour Science for Inventor and Alchemist)
- relative strengths of City Improvements. I tend to favour Science because I really like the Aqueduct and I think I undervalue Politics (because Mighty knights seem lacklustre, although they really aren't)
- evaluation of Barbarian threat
--- how much to give up for that crucial Wheat you are lacking
--- how much to squeeze out of opponents in exchange for that same Wheat if you have it)
- use and management of knights
--- when is it worth fighting for the Defender VP?
--- when is it worth deactivating a knight to move it, or to kick out an opposing knight, or to move the Robber?
- Commodities vs. Resources
--- if you're at your hand limit, when do you prefer holding onto Commodities to try to get to that Metropolis vs. resources to build a new City/Settlement?
I have thoughts on those issues, but I think C+K introduces a lot more subtlety.
OTOH, I don't think Seafarers adds much to the game. Island hopping isn't that fun to me.
* this is not to say that I am competitive at all. I'm not good at card counting. I know it's important, but I don't try very hard to do it.