Indonesia/Malaysia/Majapahit/Srivijaya etc (i'd prefer Majapahit) are a great idea as i've said (with a lot more support than I thought I had) in other threads.
A good UA for them would be something to reflect their archipelago origins, such as "Glory of the Archipelago" - ie: all coast tiles produce +1 food (indonesia has 250,000,000 people after all, it's the world's 4th largest country in population). Or: embarked units have +1 movement and +1 sight. Or: Harbours provide +1 happiness. Or something. I'm leaning towards +1 food for water tiles. Also you wouldn't want to make them too similar to Polynesia who got their ability because of their legendary reputation as ocean explorers/colonizers. +1 sight is more an exploring thing i would give to portugal maybe, or even messing with embarkment could be saved for the vikings who are famous for their longboats.
Their start bias would be to seek coast, avoid desert.
Their unique building could be a garden that provides +happiness and +culture or a harbour that does so. Unique building could be a naval unit (their navy apparently defeated that of Kublai Khan) or the Keris warrior with his wavy blade - a replacement for the swordsman or longswordsman. I also liked the idea for a garden replacement.
Favoured victory could be cultural or diplomatic.
Other civs i'd like to see personally (I mostly look for civs to fill up gaps in the world map like the indonesian archipelago, or ones we havent done before):
Korea
Vikings/Norse
Zulu
Portugal
Carthage
Mayans
Zulu's could have the
Impi (replaces spearman, costs either more or the same, strength 9 and +10% when neighboring friendly unit, stacks with the honor policy and great generals - it would be more historically accurate to make this guy require iron, but unless you make him a pikeman replacement which would suck because spearmen much better there isnt any way to do this) and Unique Improvement the
Kraal which is a much better pasture. Perhaps +1 production and +1 food from a normal pasture? Zulu capital would be
Ulundi not Zimbabwe like in previous games (WTH Zimbabwe?). Zulus would seek cows and maybe plains. UA could be something to do with great generals, you'd have to make sure it didn't overlap with China and Mongolia I guess. Or just a general boost to all units with a unit in a neighboring tile to reflect the impressive battle tactics used by the Zulu - you'd then take that bonus away from the impi and make him strength 10 instead of 9. Favoured victory would be domination.
Would be funny if the Mayan UA was that they had to win by 2012 or lose automatically

.
I agree that a harbour replacement with extra gold for carthage is accurate, interesting and cool.
I would like to see unique embarked and trireme graphics for more civs (it seems silly to have china embarking as a european style ship pre-industrial era). Asian nations could have something like this:
http://www.youtube.com/watch?v=TfNoOFUx5-I as an embarked graphics and something like this:
clicky Middle Eastern civs could use this style:
http://www.alrsaildesign.com/images/DHOW60C_small.jpg