That Independent Kingdoms thread is one of my favorites, especially after Johnny5446's post about Geoff the Slug. I'm definitely in support of that idea.
Really I think the key point is that 'minor civilizations' (or Independent Kingdoms or whatever they might be called) should be significant powers. They could grow in power over time fast enough to remain significant throughout the game, or they could start out much more powerful than actual players and gain power slower (or not at all). Barbarians in Civ IV are never significant powers, just nuisances, and minor civs in GC2 are exploitable pushovers. Neither pose challenges or interesting options.
With all of Brad's references to LOTR, I'd love to see unequal starting players. Maybe 30 players, but only a portion are true competitors on your level. Say, the Rohan who are large and active versus a more minor power like the Ents or Tom Bombadil, who are powerful, but players to be courted or worked around rather than full fledged empires trying to take control.
And those are great examples. The Ents and Tom Bombadil are extremely powerful entities, but with no will for conquest - they just want to be left alone, really. Bombadil is pretty much godlike within his own small realm, to the point where not even the most powerful object left in Middle Earth affected him. And the Ents utterly annihilated a great portion of Saruman's forces with almost no effort or losses and tore down Isengard's walls with hardly any effort (I love that's described in the books - like how a tree's roots can crush stone over a long time, but much faster). Then after that, they completely annihilated a huge force of Sauron's orcs that was great enough to have challenged the riders of Rohan on their way to the defense of Minas Tirith. Not to mention Treebeard mentioned that the strength of trolls compared to ents is like the strength of a child compared to an adult.
So yeah - independent kingdoms like that would be awesome. And, even though they shouldn't really expand, if you piss them off they should still come for you - like when Saruman started harvesting Fangorn for lumber.