Carthages UA (and to some extent, the UU elephants) struck me as being lazy solutions to what they wanted to do. So I gave it some thought:
I feel it would be better if only a Great General could enter a mountain tile, but other units could enter a mountain tile that had a GG in it. I think this better simulates Hannibal leading his army through the Alps, rather than just a having a wall of elephants climbing over them.
Free harbors are a bit lazy as well, a UB replacing the harbor or the lighthouse had been a better idea.
Now, unless the past Civ games were completely wrong, mercenaries were a big part of Carthages armies. This strikes me as the perfect idea for a UA. A lazy solution would be to make units cheaper to purchase. Another idea might be either 1) the ability to buy units from allied (Militaristic) City states or 2) that all allied city states will give you units, although non-militaristic city states do so less frequently. Now that CS give unique units, this would certainly give that foreign, mercenary feel to a Punic army. There's even a fair chance you'd get elephants, if a UB would replace the ones we got.
I dunno, just some ideas I had.