You may want to start with http://webempoweredchurch.com/ - they offer a package based on TYPO3 for free and it's supposed to be designed to get you up and running quickly. If I remember correctly, Irving Bible Church is one of their users and had a pretty decent website design.
I've been investigating Joomla for our own church and it seems relatively friendly, but still quite a bit of work. There were some reviews on Open Source CMS software where TYPO3 wasn't getting very good press from some people as TYPO3 itself is more of a CM Framework. The general developer response was that if it took so long to understand it and get up to speed, they'd rather build their own. (Not something I necessarily agree with, but I can see where they're coming from.) You can check out a bunch of open source CMS offerings at http://www.opensourcecms.com/
I'd probably investigate the WEC solution as something of interest and see how well it works. They have a version you can download and try out. You can also use something like XAMPP or even the Joomla Standalone Server as possibilities to try out Joomla locally. I saw the Joomla just released their next beta - v1.5. That may be worth playing with, but as they noted - not a good idea to deploy to a production site.
Let us know what you find out. I'm sure others would like to know what you choose and why.
In Him,
-Peter