You can just have your army move slower due to having to recon against ambushes etc. when going through a high-rebel province.

Instead of airlifts maybe think about shiptransport of troops, needing harbors to reach provinces fast makes the map more interesting.
(plus they 're restricted to sea/rivers, it also makes the game more realistic)

Due to the nature of my map implementation I can't make rivers. As for sea it's problematic as well since it's an island so more than half of provinces are coastal... Maybe if I restricted it to movement between harbours...

But, I was thinking, maybe for this game resign from traditional movement? I mean, there are mere 16 provinces total, that's not a lot of space to move around. Maybe allow instant "teleportation" of player units and use some sort of "logistic capacity" to limit how many units can be moved each turn?

Like this:

- you can move 2 units per turn, +1 if a lot of mobile units in the army, +1 if good road system,+ 1 if not moved anything in the previous turn
- you can move only to a province that is controled by you or is neighbouring a province controled by you

- heavy units can't enter mountainous provinces

You can call it helicopter transport, maybe allow the army units themselves to move independently but at a much much slower rate ?

Actually needing a helicopter base for this and having the province it is in influence it would make the game more interesting.

Well, I like helicopters, but I hesitate, it's kind of unrealistic to move all/majority of forces by helicopters if this is a banana republic. That army simply can't be that rich/advanced. Maybe more like small strike groups of special forces that use helicopters to deal precise counter insurgency strikes?

But I like military bases of some sort too, I also feel it could make the game more interesting. But how exactly could these work?

My idea is that there are like 16-25 provinces total (managable to a player and has the feel of a banana republic on an island). There is one capital city province, 3-4 city provinces, several standard provinces like 3 per city (just countryside with farms, maybe some mines) and some wastelands (mountains/swamps) that are supposed to be breeding grounds of rebels.

So, I wonder if there could be some military bases in some provinces as well that would affect nearby territory maybe? Or maybe use cities as supply points for army?

Some interesting links to fuel the imagination

http://en.wikipedia.org/wiki/Counter-insurgency (a lot of COIN (counter insurgency) stuff)

http://en.wikipedia.org/wiki/Counter-insurgency_aircraft (counter insurgency aircraft, an interesting concept...)

http://en.wikipedia.org/wiki/United_Self-Defense_Forces_of_Colombia (AUC, a paramilitary organization, half friend-half enemy)

And an interesting wall of text:

David Galula

David Galula gained his practical experience in counter-insurgency as a French officer in the Algerian War. His theory of counterinsurgency is not primarily military, but a combination of military, political and social actions under the strong control of a single authority.

Galula proposes four "laws" for counterinsurgency:[8]

1. The aim of the war is to gain the support of the population rather than control of territory.
2. Most of the population will be neutral in the conflict; support of the masses can be obtained with the help of an active friendly minority.
3. Support of the population may be lost. The population must be efficiently protected to allow it to cooperate without fear of retribution by the opposite party.
4. Order enforcement should be done progressively by removing or driving away armed opponents, then gaining support of the population, and eventually strengthening positions by building infrastructure and setting long-term relationships with the population. This must be done area by area, using a pacified territory as a basis of operation to conquer a neighbouring area.

Galula contends that:

A victory [in a counterinsurgency] is not the destruction in a given area of the insurgent's forces and his political organization. ... A victory is that plus the permanent isolation of the insurgent from the population, isolation not enforced upon the population, but maintained by and with the population. ... In conventional warfare, strength is assessed according to military or other tangible criteria, such as the number of divisions, the position they hold, the industrial resources, etc. In revolutionary warfare, strength must be assessed by the extent of support from the population as measured in terms of political organization at the grass roots. The counterinsurgent reaches a position of strength when his power is embedded in a political organization issuing from, and firmly supported by, the population.[9]

With his four principles in mind, Galula goes on to describe a general military and political strategy to put them into operation in an area that is under full insurgent control:

In a Selected Area

1. Concentrate enough armed forces to destroy or to expel the main body of armed insurgents.
2. Detach for the area sufficient troops to oppose an insurgent's comeback in strength, install these troops in the hamlets, villages, and towns where the population lives.
3. Establish contact with the population, control its movements in order to cut off its links with the guerrillas.
4. Destroy the local insurgent political organization.
5. Set up, by means of elections, new provisional local authorities.
6. Test those authorities by assigning them various concrete tasks. Replace the softs and the incompetents, give full support to the active leaders. Organize self-defense units.
7. Group and educate the leaders in a national political movement.
8. Win over or suppress the last insurgent remnants.[9]

According to Galula, some of these steps can be skipped in areas that are only partially under insurgent control, and most of them are unnecessary in areas already controlled by the government.[9] Thus the essence of counterinsurgency warfare is summed up by Galula as "Build (or rebuild) a political machine from the population upward."[10]