Augustus: Industrious to collect all of the Shiny Wonders, and Praetorians to crush a neighbor.
Roosevelt: Industrious to collect all of the Shiny Wonders, and Organized to keep the upkeep costs from bankrupting you. Also, both traits speed up the production of some of the most important buildings in the game (Forges, Courthouses, & Factories).
Darius: Financial + Organized to give you a rock-solid economy, and Immortals to knock off a neighbor.
Lizzy: Financial to boost your economy, Philosophical to give you a good introduction to Great People. Also, Redcoats are pretty solid (not as game-breaking as they used to be, but still good) and the Stock Exchanges will give you some extra cash.
Mansa Musa: Spiritual to give you the freedom to play with your civics, Financial to power your economy. Skirmishers make you all-but-immune to early aggression, and the Mint gives you some extra cash.
Those are the first five that come to mind for me. Tanktunker's point about the complexity of Civ4 is valid, and I agree that the best way to learn is simply to play. That said, I think that some of the traits (Financial, Organized) are a lot easier to play than others (Imperialistic, Aggressive). Still, if you play on Settler, it should be nearly impossible to lose with any leader or strategy....