I always play random leader, so I don't see changing that.
The only time I pick a specific leader is if I decide to go on an achievement binge and I need a particular leader to advance my goals, but based on Civ5, I doubt I'll be doing that for some time.
Map type is normally continents of some sort, or maybe random. (I wish I could randomise a subset of the maps as there are some I just don't like.)
I don't normally randomise the rest, I prefer standard settings for age, etc.
I haven't decided on speed...probably standard and then up to epic (or the equivalent) once I'm comfortable with the game mechanics.
Difficulty will start either one or two levels below Prince, and will move up each time I beat the game, and down each time I lose three games in a row, until I find a level at which I feel comfortable, i.e. win some lose some, and then settle in to learn and eventually move up more conservatively.