My girlfriend is playing the Sims Medeival, which seems a lot like what I've seen of Europea Universalis (or another one made by the same people, focuses on europe but you get dynsasties and shit), except of course that it's primarily a sims game. But it's fun. The user basically plays the role of "The Watcher" or God, because stupid sim people are too stupid to take care of themselves, hence the need for Kings/Queens that you direct. There seem to be two options for when you establish religion, either a "Peteran" church of nice monks, or a "Jacoban" church which is basically stereotypically evil medieval Catholicism.
Makes me want to play something vaguely similar, but I'm sure I don't have the time, nor much patience for learning a game like Europa. I could always boot up Age of Mythology again, but I've played the crap out of that game already. Mostly I'm just playing the video game version of Magic: The Gathering, so that's not depressing at all. :P