Shaka is fun with his half price UB barracks/mini courthouse, in case you plan on continuing with some aggressive expansion once you run out of space.
I also like early peaceful Rexing with Zara, as he can easily set up for a strong economy, while aiming for some rewarding Oromo action later. If you do expand to 10-15 cities in the BCs, then ORG discount already makes a noticeable difference, and half price courthouses are quite valuable.