Perhaps you've noticed that with the exception of Russia, Civ has never had a good civ from the polar regions. I think perhaps the Aleuts, or even including the Vikings again, would be good ideas. Aleut UU could be a sled-mounted warrior (can you think of something better?) and Vikings could get a replacement for galleys.
Yes, I am aware than Scandinavia has returned in PtW, but consider the Aleuts.
On the other end, few civs are located in the deserts, when many successful civs have started there. For instance, how about an eastern african civ? There's always been lots of room between Egypt and Zululand. Also, the Aboriginies (sorry if that's spelled wrong) would fit the bill nicely. The UUs wouldn't be too hard to find.
If you have ideas for other civs, post them here. (As if that wasn't already obvious)
Pardon me if my rants made me sound like an idiot.