First off, what difficulty are you playing at?
As for goverments, yes, you absolutely have to tear down the old ones and build you own. It doesn´t take to much time (11 turns at most) and doesn´t affect recruitment, as recruitment comes from the Regional and Native barracks, and with your own Goverment installed you can build more of these, and so get even better units.
Others can answer your questions better.