My votes in order of priority (with a little added plea for each) :
1 Poland - would fill one of the few 'gaps' in Europe, and was one of the great powers til late 1700's (at least in size). Great history with Sweden(Vikings), Russia, Germany and Ottomans. Unique unit could be
Lancer (heavy cavalry) 7-3-3? which retained lance, sword and light armor into 1700's and was highly effective against the Turks, Cossacks, AND EVEN the pike squares of the west. A cool shock unit for the enlightenment era.
Tons of great leaders available including John Sobieski who routed the Ottomans at Vienna in 1683 with the above unique unit

.
2 Tibet - good unique unit, fun and interactive location, child leader would be fun too. Tibet has a unique culture stretching over thousands of years and was an imperial state for hundreds of years (even allying with the Arabs at one point versus the Chinese). Plus I think Asia needs at least one more civ, since the southeast isn't going to get one. Great leaders such as Khrisong Detsen too!
3 Portugal - was first of western exploring powers and a caravel special unit would give them the jump start they had historically (when they dominated the Indian ocean and contended with the Ottomans and Indians there). They'd be fun to play too as the first real maritime power in the gunpowder(ish) era (they were successful against Ottomans/Indians due to their naval power), and have an ample stock of great leaders (Henry the Navigator, Francisco de Almeida, and Affonso de Abuquerque come to mind).
near misses in order
4 Hungary - great unique unit in Horse Archer, fun history raiding western Europe. Just not enough map room and slots.
5 Songhai or Mali - a unique cultural region but...
6 Maya - great civ, but would probably overcrowd region. Otherwise I'd rate them higher.
and some quick 'slams':
Dutch - no room, sorry!
Romania - derived from Roman settlers anyway. No unique unit jumps out. Purely regional power anyway.
Sioux - as my first post, the Iroquois already have their unit!!!
Aberigenee - VERY local, VERY limited tech. Posed no unusual opposition to outside settlement. Polynesians much more widespread (i.e. civ-worthy) and will probably get to region before west anyway if you need opposition there.
Saracen - weren't these just the
Arabs anyway? Better to suggest the Berbers if you need another Islamic civ (not that their history begins there by any means).
Thailand - as first post, just get edged out by other civs in all areas.
Czechs - region too crowded again. Second to Hungarians in timespan, unique unit(personal pref), area of influence anyway.