Would it be easy / worth it for you to change the cap(s) based on the actual map size? So that an enormous map that was very underpopulated had a higher maximum than a smaller map underpopulated by the same amount?
See below

I had that as my original plan until something dawned on me- By default larger maps have more players! I know, it's amazing (that I didn't think of that originally and it would have saved me a lot of time).Thinking about it, a universal -- albeit potentially very very slow -- way to do it would be to calculate the starting distance based on the size of the map and the number of players; then, if not all players could be placed, decrement the starting distance and try again, iterating until you reach the minimum amount of space between cities or you succeed.
I have no idea if that's actually possible or not, though -- given that your initial buffer resulted in players missing, I suspect it isn't at least at the moment (I'm not on our gaming computer, so I can't go look at the lua code to see).

What happens is that the total number of tiles per player stays fairly consistent using the default map sizes and the default number of players. This means the only thing we really need to handle better is games using a non-standard number of players so I greatly simplified things. We could stand to have some alterations to the starting plot "fertility" requirements based on the actual player count but certain things like the map options (sea level, rainfall, world age) aren't even exposed to the starting plot calculations so a script like this that's intended to work with any map script, including custom ones has to work on best guess a lot of the time.
There is still room for improvement but I guess deep down inside I was hoping for more patches this early in the game's life since there are quite a few bugs that still need fixing, I guess I envisioned this script as more of a temporary fix until we had a more stable game and the full mod tools. Compared to Civ 4 & 5 it is substantially more complicated to handle map scripts and custom map settings since we can't simply define those in the map script itself and this makes it tougher to make a script like this as user-customizable as it needs to be