A typical rule of thumb would be that an established company sets aside around 15% of the outstanding shares at any point in time for employee options. Those get split up among employees based on their contributions.

Depending how key these VPs are relative to other employees you have (remember to give them something also) or expect to hire, you might give them 2-5% each.

This assumes that you are an established company. If one of the VPs is going to quintuple the size of the business, they might push for being more of a 'partner'.