Not unless each subrace had its own government and territory, which does not appear to be the case – they seem to live together as a dominant caste and a subordinate caste, with the white-on-left-sides ruling the whole planet. Which is more relevant to the real-life American situation the episode was meant to anviliciously parody.
The home world (well, home system, really) of the Moties do not have any kind of unified government in Jerry Pournelle & Larry Niven’s The Mote In God’s Eye and it’s sequel The Gripping Hand.
Marion Zimmer Bradley’s Darkover series was very feudal.
Good call-out HookerChemical - I immediately thought of The Dispossessed as well.
For a certain value of ‘governed,’ of course. 
In Lois McMaster Bujold’s Vorkosigan novels planetary governments seem to be the most common (with a few interstellar empires, of up to maybe a dozen or so planets), but in The Warrior’s Apprentice the planet Tau Verde IV–which is implied to be a pretty backwards place–has at least two sub-planetary nations (Felice and Pelias) who wind up fighting a war with each other, including considerable off-planet fighting in the Tau Verde system’s asteroid belt. The planet Jackson’s Whole in the same universe is also notoriously disunited; instead of nation-states, it’s ruled by anarcho-capitalism-run-amok “Houses” and “Great Houses”, which style themselves as an aristocracy (with “Barons” as heads of Houses) but tend to be considered gangsters (albeit sometimes useful gangsters) by everyone else in the known galaxy.
(The inhabitants of all these planets are descendants of Earth-human colonists; there’s no intelligent extraterrestrial life in the Vorkosigan saga universe, although some of the humans in that universe have been the subject of fairly extensive genetic modification.)
Well, if the claims of the characters is any guide (the premise of the episode in part is that Bele and Lokai were so radicalized and hardened in their enmity that neither could be trusted to give an unbiased description of their circumstances), Bele’s people (black on the right side) dominated Lokai’s people (black on the left side) with no indication of parity in control of the planet, though they did manage mutual extinction.
Related, there have been numerous TNG and Voyager episodes where the Starfleet characters get caught up in some planet’s world war.
Jonas Quinn’s homeworld was divided into three nation-states locked in a three way cold war.
There was an episode of TNG where a planet was divided into two different nations; one of whom was a candidate for Federation membership. Picard & Crusher ended up trapped in a cave. VOY had an episode where the ship got stuck in orbit around a planet with an anomaly the caused time to pass so quickly from Voyager influenced their mythology & religion and the planet went from a tribal period to the rise of nation-states to the formation of a Central Protectorate.
Terra in the original Battlestar Galactica was divided between the Western Nationalists and the Eastern Alliance; which were locked in a cold war both and both had off world colonies.
Harry Turtledove’s A World of Difference is set on a alternate version of Mars (which supports intelligent life) where there are separate nations. The plot of the story is competing American and Soviet missions to the planet end up allying with competing local nations and fighting a proxy war.
Another ST:TOS ep was A Private Little War. Warring clans being supplied by the Fed and Klingons
The Iotians of A Piece of the Action probably qualify, too. Not a unified world government anyways. At least, not until Kirk interferes.
The Ringworld had many autonomous groups.
It’s been a long time since I read it. I don’t remember if there were any governments larger than a city-state.
TOS also had the infamous* Omega Glory*, with the battle between the Yangs and the Comms, A Piece of the Action, where Oxmyx and Krako’s gangs were effectively rulers, and A Private Little War, with the villagers and the hill people,
That’s what I came here to post. There are three to come to mind - Jonas Quinn’s homeworld, with three major powers in a stalemate; the world with the drones and fusion reactor looking to trade for heavy water; and one world that was okay until the Stargate opened and provoked a religious civil war, triggering a conflict with their neighbours.
Does Dune count? The entire planet of Arrakis is legally within House Atreides’ fiefdom, but the Fremen sietches are for all intents and purposes independent polities in and of themselves. There’s also passing mention made of the “Houses Minor” - families that held seats in the Landsraat but whose territory was less than an entire planet.
There is one Sci-Fi story (by Asimov perhaps) which plays on this premise. The planet has one world government: which deals with interstellar affairs. But it is comprised of hundreds of distinct governments ruling different parts of the planet with different assorted rules. I thought it made great sense. On Earth we have different national and sub national (and lower) levels of government, often times from different political parties.
The concept of local and national will be quite different in such a planet with interstellar spacefaring technology.
In the Phantom Menace, the Naboo and the Gungans appear to independent.
Do the Ewoks and the Empire count on Endor?
Oz has sovereign states for Munchkins, Winkies, Quadlings and Gillikins. Gulliver’s world had states for Liliputians, Brobdingnagians and Huoynms.
The Dogtown Tourist Agency by Jack Vance is set on a remote planet with different areas controlled by three different space empires. It’s where the empires’ borders meet and so also where they discuss mutual problems, etc.
There’s a fledgling tourist industry in the human-controlled area (giving tours of the local indigent alien tribes, scenery, etc) but it’s unclear if more than just ambassadorial staff from the other two civilisations are there. And there’s virtually no communication with them outside official channels.
The Left Hand of Darkness was my first thought, but it’s already been mentioned.
OTOH, no one has mentioned Barsoom. The Red Martians had numerous city-states with countless tribes of Green Martians until John Carter conquered them all and brought them under Helium’s hegemony. There were also separate societies of Yellow, Black, and White Martians, all of which eventually became part of his empire. Plus those guys with the detachable heads. Did he conquer them, too? I don’t remember.
Iain Banks’ “Against A Dark Background” is set on a planet overrun with nation states, local governments, communes, etc. They all have a patchwork of rules and agreements that stretch back over thousands of years, resulting in an incredibly jumbled system of interlocking governments with borders that shift here and there as if the planet had been gerrmandered by various power-made types over thousands of years, which is probably the case. Things are at peace on the planet, Banks’ use of the fractured subplanetary governments wasn’t so much to provide a framework for war as to have some fun parodying Europe’s collection of tiny nations.
Niven and Pournell have already been mentioned, but in Footfall, the alien invaders are all from one polity (though even on the ship, a divide has started to form in the time since launch), but the planet they came from has a number of separate “herds”, and they’re not at all surprised to find that we have separate “herds”, either.