Thanks for the reference, Judge. I've got an essay on merchant guilds, but I've neglected the series as I'm bringing my current novel in to the finish line (two more days!). I'd be happy to respond to ad hoc questions here.
Let me start by answered unasked.
"...states not run by feudal overlords." There are examples for this. The most ready to hand would be the independent city-state. Venice, famously, but also Florence or Siena or Parma. A number of German cities were theoretically under the Emperor, but effectively they ruled themselves. Having your character head to an important, independent city would be natural and would afford all sorts of possibilities.
As for merchant guilds, those were not independent states in any sense. These guilds were very much part of the city in which they existed. In many cases, they formed a significant part of the ruling body. There's no such thing as a rural merchant guild, so you're pretty much back in the city again.
I'm trying to think of a third form. Several entities called themselves republics, but were really just a powerful town and the surrounding countryside. You could go with tribes, but tribes of any substance usually wind up making kings anyway. Cities are really the place to go, especially one that is rival or competitor to that king. The city might be technically subject but practically independent, with the king wanting to reassert control. Or the city could be a fully independent power with as many resources as the king has. Venice is the model here, which had a veritable empire in the eastern Mediterranean for a long while. But there are other fun examples. Rodez, where half the city was under the jurisdiction of the count, the other half the bishop. Made for interesting legal cases. Even more fun is Branschweig, which had seven (count 'em) jurisdictions, some overlapping. You probably don't want to wade into waters that deep.
Anyway, the door's open. Office hours are continuous.