The Flexagon is interesting, but it takes us back to words pretty quickly--I was thinking that the shape should be more expressive . Perhaps a fish, or a chalice, or bread. Or for Trinity Sunday it could be a bunch of nested triangles.
Printing isn't an issue at all. I'd just create a mock-up first, then number all the panels and lay the paper out flat again. I'd set-up a document in Adobe InDesign with the fold lines as the guidelines, then create a layer that would have the numbers of the panels and another that was colour coded to make it easier to see how the panels would stitch together, then you just start putting your text boxes and picture boxes on top of that. Delete the guide layers and you're done!
Since most origami is made with square pieces of paper, it will print out on the church's printer just fine. Folding it, however, will be a little time consuming unless you have a bunch of volunteers (depending on the size of the service, of course)!
No comment on origami - just wanted to say hi, Tay, since I saw a name I recognized from YDS....