Hey, don't get discouraged so fast.
I don't know if this will help at all, but here's what I did, and it worked out okay in my game.
First, note that I also let all my casters mix and match spell slots (e.g. one 3rd level slot can be used for a 2nd level and 1st level spell). Power points, mana, whatever you want to call it. I only mention this because when you see what I took away from the cleric, you need to realize I was also compensating for this supreme flexibility. I would not suggest taking away quite as much if you want to keep spell slots rigid.
No domains--No domain spell lists, no domain powers, no extra domain spell.
Prohibited from using non-blunt weapons. This further restricts options since clerics already get only simple weapons.
In exchange: Spontaneous casting. "Mana" spell point system. But what about the spell list?
All spells were "Gifts from the Immortals." No specified number of spells known, no specified spell list. I gave the cleric a small number of spells to start with. In the course of adventuring, sometimes a new "gift" would come as a reward for a truly great deed, a case of extreme need, or devout prayer (involving sacrifice of wealth, magic, etc. and Knowledge(religion) checks). This led to a very different sense of how arcane and divine magic works because the cleric was more the recipient and executor of divine power rather than a "divine scholar" who chose what spells to know or prepare. New spells ("gifts") would be granted in a spectacular and usually nonvoluntary manner--sometimes it was not immediately clear what spell was obtained. An example is when the party was faced with certain death by enemies given a river blocking their escape. The cleric was told that her hands began glowing and that she felt an urge to pet the party's horses, and then to lead them to the river. Just in time, she figured out what was going on and they were able to cross and escape. The players all had more of a "wow, she made the horses walk on water!" reaction than a "cool, she got Water Walking." Afterwards, I just said "deduct 3 current mana" and add Water Walking to your spell list.
I found that with cleric spells, so many seem vital that it's hard to find a good number of spells to have a spontaneous caster know at each level. Some spells are just more essential than others, and those do not constitute a constant proportion of the list at each spell level. By retaining control over the individual's spell list, I was able to make sure she had the spells she needed but not so many that she became overpowered. Also, since new spells came over the course of adventures and not just at level-up, things had more of a mystical, in-game feel. Also, it was clear that every cleric has an individualized spell list, even if from the same religion. Sometimes help from another cleric was necessary even for a spell of an accessible level, because the PC didn't have that particular "gift" (e.g. Hide from Undead"). Also, some spell names were customized to the religion, or even tweaked for balance (e.g. Silence) or uniqueness.
Incidentally, by 6th level, the PC cleric in my campaign had access to 10 0-level spells, 8 1st-level spells, 11 2nd-level spells, and 6 3rd-level spells. Why, you might ask, did she have more 2nd-level spells than 1st? Because it just worked out that way in the game. Perhaps more 2nd-level spells seemed necessary than 1st-level ones? One thing for sure--if the cleric is the "medic," a lot of the healing and restoring spells you just want the cleric to have, period. It's some of the more offensive or broad utility spells where you start to worry about a spontaneous caster getting too powerful. One solution--instead of trying to come up with a mathematically-elegant formula for all spells known, just make a list of spells that the cleric DEFINITELY gets. Don't worry about how many there are, as long as you feel that they are necessary and not overpowering (for instance, you might add all the healing spells right off the bat). Then, decide on a small number of spells known IN ADDITION to the essentials list. This way, the player has to make tough choices like a sorceror about spells known, but doesn't get forced to just pick "medic" spells, which might make all PC clerics identical by necessity. I can say it is very nice not to have PCs die because the cleric didn't memorize the right healing/restoration spell (remove curse, remove disease, remove blindness, etc. etc.). Somehow, it just seems crazy to me that you have to prepare in advance to be able to cure something like blindness. I think a cleric should be able to deal with that problem on the spot--provided her god gave her the ability to remedy it in the first place, of course! If she doesn't have the ability, she knows to be extra careful about certain situations, but doesn't have to feel stupid about what was and wasn't prepared. Also, I as a DM know what she can handle because I know the spell list, and I don't have to hint at spell choices, feel bad for throwing encounters at the party that they can't handle because so many cures for various ills all cluster at 3rd spell level, or change the encounters to pull punches.
Maybe none of this is right for you, but I'm sure more ideas will come. Just keep thinking about the problem.
Good luck!
Darn that slowdown...
