I think Par 56's will suit your needs well. I've used Par 64's in an area similar to your stage and I was just not satisfied with the results. The cans were too big, too hot, and the light was too scattered (granted that could have been the lamps).
Anyway, you're probably looking at needing somewhere in the ballpark of 20 feet trussing for your back/upstage lighting (i.e. the main 'light show'). 16 cans should sufficiently get you off the ground. You'll probably want to put medium flood lamps in them.
Also, you should consider the use of front lighting in addition to your upstage lighting. This will provide light so you can see faces when people are on stage. This gives you the benefit of utilizing the upstage lights for desired effects rather than having the sole purpose of providing light for coverage's sake. Front lighting could be for 'wash' (pure coverage) or for 'spots' (individual places to accent with light from the front - i.e. a performer).
Hope something helps.