I think the perfect CEO for Uber is Vishal Sikka. PhD in AI (cars!) from Stanford - Startup founder - Revitalized SAP with in-memory HANA database - Managed Infosys with 200k employees.
Vishal Sikka has both exceptional techincal skills and management experience. And he is available for a new job!
Like Travis, Sikka is very bullish and calls himself a "kshatriya warrior". I think that Sikka and Travis would be quite compatible with each other.