Shoshone are more consistent, since you can pick ruins and plan around the first two at least. I always go for culture and then the unit upgrade to comp bowman for early defense and barb-killing missions. After that faith if possible, else pop, tech if I find another. (Tech seems overrated--it's a gamble whether it's something you want or something that'll take two turns to research by the time you need it...or its the tech you're almost done researching.) Shoshone shine right out of the game with their expansion bonus and pathfinder picks. However, without a faith CS or ruin, it's hard to squeeze in a religion at all.
Ethiopia is a gamble, as religious civ bonuses tend to be, especially on higher levels. But as has been discussed, the stele is awesome, and works well with both tradition and liberty. Ethiopia also shines in the early game, but more towards the mid game once religion starts to pay dividends.
Both of the combat bonuses are almost insignificant, especially insofar as the compare to each other.
The civs tend to play very differently for me. I've had much more success with Shoshone, but I plan to try a Piety game with Ethiopia soon and expect good results, although Maya seem pretty much strictly better for this.