Here's an idea - three "levels" of prayer.
The first, and fastest, level is just the generic "Please <god>, help me!" - this works just like the pray option in ADoM, and the god will make a judgement on what is most urgent, and do that. It takes just one normal turn, and requires minimal piety by comparison with the other two. However, it's the most costly, piety-wise, relative to benefit gained, as well as lacking any sort of control. While the exact piety required for any given result will vary depending on the god you ascribe to, the actual result would be independent of the god. It would *always* be granted by the god you primarily ascribe to.
The second, requiring more time, can be thought of as more like a simple ritual, a prayer for something specific, such as healing, food, etc, as I listed in my previous post. This sort of prayer takes multiple normal turns (you won't die in the middle of it - the god will prevent you from dying during the wish, even from physically being sliced to death... but you'd better pray for health or equivalent, otherwise you'll be dead once the prayer finishes). It does, however, give you more choice in terms of what you pray for, and requires less piety (given the resulting action) than the basic prayer. It might also be influenced, for example, by holding a holy symbol. This prayer, you could also ask of any of the deities that you are reasonably close to, not just the one you're closest to.
The highest and most turn-consuming form of prayer, however, would require an altar to pray upon. This type of prayer would require even less by way of piety, allow you to explicitly ask for something (a la wishing), and provide you with opportunities to wish for things that you cannot get through the other methods of prayer. However, not only do you need an altar, but you may also need an appropriate sacrifice, depending on the prayer and the god to whom you pray. You could choose any god you know of (the names would be randomly-generated in each game, so you must know of the god in-game), but it must be either at their altar or the altar of a friendly deity (the god of life and the god of magic might be willing to take sacrifices/prayers from the other's altar, but I wouldn't recommend using the god of death's altar for either one).
Choice of god to pray to would matter, while relationship with that god would be the primary decider on whether a sacrifice is needed - if you're the deity's avatar, you won't need a sacrifice, and can ask for anything that doesn't contravene that deity's laws - for instance, wishing for things intended for killing from the God of Life would probably upset that god.