The answer is:
Via MyDMX: yes
Via hardware: yes
All you need to do in MyDMX is program in a fade time, which is easy to do in the edit window and tell it to "always loop" and you'll avoid any "moving forward issue".
Using a hardware controller, such as the DMX Operator, you'd set your fade time using the fade fader/slider. You can directly access your scenes via the scene buttons, provided you are in the correct bank. With the fade slider set, they'll transition over the time period specified. The scenes won't bounce around unless you want them to.
It's really what is more convenient for you at the time and the budget. The price of MyDMX is close to the cost of a DMX Operator. I guess it's a matter of what appears to be more user friendly for you.
MyDMX has a higher cost for ownership, mainly since it involves a laptop or computer, and should the computer owner split, so does MyDMX, but the dongle can always stay and be secured to a surface via security bolts or a laptop locking cable system. With a DMX Operator, you should document your scenes on paper and then label things to make it easy for the next user.
The MyDMX dongle has 4 holes in the flanged base where it can be screwed into a table, for example. On top of that, it has a slot designed for one of those laptop-type security devices.
If the church has a laptop for this application, maybe MyDMX is the way to go. If it's more of a "volunteer" thing where people swap in and out, MyDMX may appear to be more user friendly, but then again the DMX operator is very easy to use and requires minimal training for basic operations.
I'm sure higher end DMX consoles can accomodate these sort of things. This isn't anything major. It just isn't as obvious with the controllers and the higher end stuff just has way more features and functionality so something like that may be buried. But I'm 99% sure that transition fade functionality would be there.
In the end, you can do this either way. It's what you feel better with.