In order to either establish a new Minor Hellenistic Polis (polis_one) or Hellenistic Colony (helcol_one) or upgrade a helcol, you need colonists available, who come from owning a Hellenistic Metropolis (polis_three). There are only six of these on the map at the start of the game: Athenai, Korinthos, Syrkousai, Alexandreia, Ephesos and Pergamon. Thus the only factions who start with colonists are Makedonia, Ptolemaioi and Pergamon. AS don't have any Metropolii at the start, thus have no colonists available. Ironically, KH can't send out colonists, but start with a Metropolis.
You need to either conquer one of those, or upgrade a Hellenistic Polis (polis_two) into a polis_three. In order to do that, a settlement needs Hellenistic Polities 69% or above, have a market_three (Forum or equivalent, I think) and minimum gov5 (Hellenic Administration). Conversion does happen simply by having your government buildings in place, but it does go at the rate of about 1% every few years, so unless somewhere is close, this is probably going to be the bar to any upgrading, because that will take a long time.
Once you have a polis_three in your domain, for each one, you get a colonist group every 16 turns. As above, you can use this either to seed a new polis_one in a place which has a trader and Hellenistic Polities of at least 29%, or install a new helcol_one somewhere with farms_two. The latter will accelerate conversion to a Hellenistic Polities 30%, then the next level (requiring colonists again) will speed it to 50%, and finally helcol_three accelerates it to 70%.
In other words, if you're looking at somewhere with negligible levels of HP, you need to install a helcol_one first, which will speed the time to being able to install a polis_one. The problem you will have with Segestika is that it's size means you can't build the requisite level of farms, but by the time it reaches that scale, you will then be able to install a helcol_one (assuming you still hold Korinthos). In the meantime, if you want Phalangitai anywhere besides Pella, you should be aiming to install a helcol_two somewhere - Demetrias is a good option for this. You'll need two lots of colonists to do that - one for each level of helcol, and have to upgrade farms, road garrisons and install a Game Field.
The Polis and Colony are both troop-producing buildings, but give different troops. You get Greek-style levies and semi-professionals in the main out of the Polis (Hoplitai, psiloi, old-style cavalry, etc). You get Macedonian-style professionals out of the Colony (Phalangitai, Thureophoroi, Kretans, newer cavalry etc).