Hi DestinationCC and welcome to the forums.
First things I noticed, wide stage with not a very high ceiling. So you will need quite a few lights to do the job. For front lighting, I would recommend lekos in groups of 2. If your lights are hung about 15' away from the edge of the stage and roughly 12' off the ground of the stage, you will need about four 50 degree lights to do a wash from straight on. 8 lights would give you two colors, warm and cool which is common in concert settings. Leko's also offer a bit more control then PARs and LED cans so you won't have any spill on the edges of the stage. You can also put gobos in them, which can be steal or glass and literally project anything from words to pictures (though the glass photo ones are really expensive). 8 lekos with 2 good dimmer packs, like
these should be around 3 grand or so. I would also only recommend Source Four Lekos. They are more expensive, but the standard and well worth the cost.
For stage light, I would go LED for sure. Less heat, less power. 12
Opti 30 Tri's with 25 degree lens kits would work well and can be had for around 4 grand or so. They should wash the stage well and also not look like pixels of RGB when you look at them, just solid groups of color like PARs.
The extra grand for cabling and control. A software solution in this case will most likely be easiest, like
MyDMX. It will allow you to grow the number of lights you have as the church grows. It would also probably be the easiest to learn as well. And make sure you get a DMX splitter as well, like
DMX Branch/4. Very good idea to have, boost signal, prevents damage, and makes cables runs shorter and easier. Also make sure to only use DMX cable as well.
Let us know if you have any questions, but I think the system I suggested above should serve you well. Once again, welcome.