Lighting Software(PC) vs. Lighting Console

To be honest, I would not recommend Express or Obsession II for moving lights and LEDs, as they were never really designed for them.
(LEDs didn't even exist back then!)

Given the size of your lighting rig and your budget, I would usually recommend a brand-new ETC SmartFade ML console.
- Looking online I found it for approx. $2000 from several retailers, you might even find it cheaper.

This has two DMX universes and will control up to 24 'multi-parameter' fixtures (eg your PAR46 LEDs and Design Spots) plus 48 dimming or switching channels, so you'll have plenty of space for future expansion.

SmartFade ML has effects, submasters, direct selects for busking and fast programming and a theatre stack so works very well for this kind of space.

The free SmartSoft application then gives you a live onscreen display, and an offline editor.

If you think you're likely to expand beyond the 24 moving lights of SmartFade ML and your budget will stretch a little further, then the next step up would be an ETC Element.

I have an Express 250 with 5 generic LED PARs. The LED units have been great addition to our small inventory. But, control is a bit of a bother. I was able to create fixture definitions for them, but the device parameter labels only had CMY, not RGB. So Cyan is used for Blue, Magenta for Red and Yellow for Green. Next comes the issue of setting levels. Working with one fixture is fine, but if I want the same values in the other devices, the easiest way I've found is to define groups for the Red, Blue, Green and Intensity channels.

We are moving to a new venue that already has a Hog PC to control their lights. I've used MagicQ PC before, and finally got half an understanding of how it worked. My main complaint with PC based systems is the lack of real knobs and dedicated buttons. Being able to reach over and adjust something on the fly is invaluable. Especially if I just need to add an extra light(or two), and will need to fade it out with the cue fading how does one click the go button on-screen, and fade down a virtual fader at the same time.

I've had my eye on getting an ION, but that is going to have to wait until we finish raising money for our new building.

 I would agree with the above.  As a long-time Expression/Express/Emphasis user, integration of LED (kinda ok) and moving lights (quite a pain) is a challenge.  the ML referenced above will be a great solution assuming the basic size of the rig described.  If you really are serious about expanding your rig, the ML may quickly run out of "headroom" in terms of efficient fixture count.  The console will deal with a fairly high number of fixtures at 24, but it gets kind of hard to operate them quickly when programming.  At that point you may need to consider Element/Ion to be quick.

However, I'd also say as far as selection between software and "hardware" based solutions, it really is more a question of how you (and/or your volunteers) like to work.  My general rule-of-thumb is that if you have a background in theatrical controls operation, you will likely have a difficult time adapting to a wholly software-based system.  If you have no console "habits" many software-based make make perfect sense to you, but it will depend on your level of "computer intimidation".  The biggest problem is selecting a software package that actually does the things that you need it to efficiently.  There are a lot of software systems that claim they work well with X-Y-Z , but when you get into programming they are difficult to navigate.

DEMO, DEMO, DEMO.  Ask around other churches in the area and see if they have the kind of setup you need to run, or ask a local dealer if they can demo a console for you (ideally at your facility).  Get off-line version of software (both hardware consoles and software).  Most of these will have full operability, they just won't be able to actually control lights. 

Good luck!