1. As I understand it, it happens once a city in Italy becomes a Huge City...or perhaps it was the Marius Reforms. I can't remember exactly, but it's not linked to an MIC level. Personally, the Hysteroi Pezhetairoi aren't anything that great, they only have one more defense then regular Pez. as I recall.

2. No, you can't hire them. You can recruit them however with a level 3 or 4 government in certain provinces in Africa and the Far-East

3. Government buildings are mainly there for A) Unit recruitment, since they determine how high your barracks can go, B) The bonus' they give, and C) Roleplay value.

4. I think your best bit is a level 3 governement on Crete, if playing as Macedonia which you seem to be.