I've heard about Easy Worship, but have no experience with it. At my church we use MediaShout, which works well for what it's needed for (we used to occasionally run videos from it, but now it's only used for lyrics 90% of the time since we bought a Tricaster). It's fairly stable but some users occasionally have issues.
At a conference this week I had some time to play with ProPresenter, another popular choice. It seems to be more user-friendly (good if you have untrained volunteers). From what I've heard it's very stable and more efficient with system resources than MediaShout. It also has many cool bells and whistles such as overlaying lyrics over a Firewire video source. It's Mac only, while MediaShout is PC only, so that may be a deciding point for you.
If you're buying everything from scratch, I'd recommend the Mac+ProPresenter route.