...for someone who has a little bit of experience with the game but not nearly enough?

The Romans.

The organised trait (with cheap {choppable} Courthouses) allows you better opportunity to expand your empire before confronting the possibility of commerce problems.

The Praetorian unit is especially strong, and should allow you to capture plenty of cities in the early game (not so hot if you're stuck on an ocean-locked island!). This will give you greater confidence in initiating early warfare. Use in stacks and attack en masse.

The Romans.

The organised trait (with cheap {choppable} Courthouses) allows you better opportunity to expand your empire before confronting the possibility of commerce problems.

The Praetorian unit is especially strong, and should allow you to capture plenty of cities in the early game (not so hot if you're stuck on an ocean-locked island!). This will give you greater confidence in initiating early warfare. Use in stacks and attack en masse.

Of course getting reliant on an early UU could work against you just as much as it helps:p .

I'd choose a civ that fits your play style (a non-answer I know), if you want to warmonger try an Aggressive + something else leader. If you're a builder then Expansive, Philosophical or Industrious traits are good to have. Try to play some civs that don't start with Mining and aren't Financial, it makes the game a bit harder, but it can also help to make a level a good challenge if you're halfway between them. Spiritual is often underrated and can be used well to respond to different situations, but you need to micromanage your civics to get the most out of it. All the traits are useful, but some are better at certain difficulties than others (Organised goes up in value on Emperor+ for example as you don't start at -2gpt), and Financial is quite easily the best a lot of the time

I'd basically just stick with random leaders and try to maximise the benefits of their traits, so you learn to use all of them instead of relying on one specific thing in your game. Being able to adapt makes everything seem much easier and less worrying when you encounter something different.

Colony,

I was mindful of the point you make on Praetorians myself, in that it might lead to a point where you don't initiate early wars when playing any other tribe, because you don't have a unit with 8 attack strength at hand. I just feel that it's important to learn not to turtle-up completely until it's too late, and there's no better tribe than the Romans to break early-game passive play.

I was however uninclined to suggest an Industrious tribe due to 'Wonder addiction' problems. ;)

Your suggestion of 'Random' is quite a good one too!

I'd basically just stick with random leaders and try to maximise the benefits of their traits, so you learn to use all of them instead of relying on one specific thing in your game. Being able to adapt makes everything seem much easier and less worrying when you encounter something different.

This is excellent advice. Recently, I've been playing the same strategy on a large Terra map (Prince, epic) that involves an early war to pick up an AI capital, researching optics and astronomy and settling (taming) the new world before other AIs can gain a foothold. I do this using random leaders which forces me to use different tactics each game. Same basic strategy but widely different ways to implement it depending on my random leader's traits.

the choice of the leader is very dependent on your goal :
- learning? what?
- easy win?
- a change?

If you want to learn the combat subtilities, go with either romans or an aggressive leader. I used kublai kahn for a start.
If you want to gain better understanding of the tech tree, choose a financial leader. Washington or Catherine are good ones.
If you want to experiment the civics, choose a spiritual civ. My favourite is hatcheptesuh.

If you go for an easy win, choose settler level ;)

I learned the game through the following leaders

Chinese guy - not Mao (alone on an island) Brilliant for learning research, buildings, improvements and all the new stuff.
Frederick - loved the tanks in all previous civs and wanted to learn about great people
Hatty - wanted to learn about spiritualism and religion (probably isabella might have been better)
Mansu - learned to fight raging barbs option as archers suck and I struggled to defend improvements and cities with them.

I also like playing as Saladin for his traits, pity his UU sucks.

I really want to play as the Greeks but I love the skirmisher too much at the moment.

...for someone who has a little bit of experience with the game but not nearly enough?

For general game play - which is to say getting a handle on how things work - I recommend Hatshepsut. Creative means you can avoid the headache of getting early border pops into your second/third/fourth cities. Spiritual means you can experiment almost as much as you like with Civics. The Wheel + Agriculture pretty much assures you that your first worker will have something constructive to do right off the bat, and you can research Pottery right away. You are also only one tech away from your Unique Unit; War Chariots have two movement points, so you get around more easily and respond more quickly to barbarian incursions.

The Egyptians were one of the powerhouse civs of early history, and the game reflects that.

For war play - exploring how combat really works - I recommend Asoka. The Indian Unique Unit is the fast worker, which means all of your military units are the standard ones. Spiritual again means no penalty for experimenting with the war civics (Vassalage/Theocracy). This is the cure I recommend (based on my own experiences) to Buildaholics [which is why I choose Asoka instead of Ghandi - Industrious is a no-no for people trying to wean themselves away from the habit of building everything].

The religion minigame and the Great Person minigame are also important to learn, but I'm not sure which leaders are best for those (clearly, if you are trying to win by those routes, you choose Isabella or one of the Philosophical leaders respectively; but that might not be the best way to learn...)

After you are comfortable with the core ideas, I'd start working through the traits one by one, trying to figure out first what types of strategies work well with each, then how pairs of traits integrate together (for instance, figuring out how Aggressive/Expansive and Aggressive/Organized differ).