I think Keith David did a great job on the Civ5 preview trailer with his opening lines. Loved his work on Egypt's Golden Empire.
I would love to have someone like him narrate.
He has a clear voice. I think we need someone with deep and more distinct voice that resembles an old man. A voice that is associated with wisdom, age etc.