Theodora
Arcane
Honestly, I would argue that IR has more really well fleshed out starts than most Paradox games have after two years of post-release development (which is kinda impressive given how much they had to do in order to simply recover from the mess that was the launch version). You don't have to play as Rome to play an interesting start. Beyond Rome and Carthage, you've got the Diadochi, and a bunch of Greek minors all fairly distinguished.I did play as Rome because minor states are dull in Paradox games.
Would recommend Epirus or Massilia if you want something in the western Mediterranean, otherwise the Bosporan Kingdom is one of the most interesting minor starts imo, along with Bactria, which can form the Indo-Greek Kingdom. If you want to dive into a big messy empire, Antigonids or the Seleukids are obvious picks.