You have to build the highest level of Macedonian government. To do that, you need to build the 3rd level of the military colony in a city that has a 'Hellenistic Metropolis'. You gain colony points every x turns by controlling metropolises (there's a popup when there's enough points to build/upgrade a colony). It takes some time to build a city up like this (my estimate is about 100 turns).

I wouldn't say you have a lack of cavalry in the meantime, though, the lancers are a decent cavalry unit, with very good effectiveness for the cost and availability.