The minimum necessary to reach the desired mechanical results and establish the intended feel.
Well, I would say that for some games, the minimum necessary granularity would work best with a d4 and have no numbers greater than five. Your game reminds me something of a game by Paul Elliot called Totem where rocks were pulled from a bag in a way that gave probabilities of 1:3, 1:2, and 2:3 - I don't remember the mechanics well, but there may not have been numbers. I do think these kinds of games are well designed, but, if you allow only the minimum necessary granularity, then you'll turn off some gamers. (I just wouldn't be one of them.)
*Large dice pools* moves the game outside of the theater of the mind (temporarily) and onto the table more than a system where you are only dealing with a die or two does.
My sense of games is that this is where most people's mental playing space actually is: the table. My attitude has always been simulationist, in the sense that I stop believing in the numbers and dice and sheets unless they plausibly reflect something that is happening in the otherworld, rather than
being the thing that is happening. It's taken me a while to realize that this is unusual.
For instance, I don't know whether most people stop to consider whether it really matters if they have a 9 or 10 in a stat. Isn't what matters whether you succeeded or failed at a task, and by how much? This is what actually happens in the game world; as I see things all stat are are nothing more than measurement or representations, which can only be so accurate. True, you might want to have a feel for your chances going in to a task, so you might care whether your stat is 9 or 4. But this is about where your adventurers would be - they could have only vague clues about their abilities and the strength of the problem going in. Definitely when I present myself to a job interview or try to make it to a store before closing, a don't gauge my chance for success at granularity better than fifths. And none of my attributes are measured to any more accuracy than a standard deviation - if one rose or fell by less than that (say, 2 points in D&D reckoning) during the day, I would have no way of noticing. I really don't mind a certain amount of fake precision, so if people like to measure out their stats to the nearest 5%, fine with me. But when the numbers get quite large they simply become tedious to manipulate.
I personally find using the d20 system for anything other than D&D unsatisfying in and of itself, because it turns what should be it's own game into an extensive set of house rules in my gut emotional perception. So that bias on my part means that no matter how good the system, if it's not D&D but we're using D&D dice systems/rules for it, I'm already dissatisfied.
OK, but bear in mind that there are lots of other systems that used twenty siders. For instance, I mentioned Dragon Warriors earlier. Every character has ATTACK (13 for a Knight) and DEFENCE (7 for a Knight). When you attack, roll d20 and subtract the roll from your ATTACK to find the DEFENCE score you hit. Lower rolls a better, so a roll of 20 always misses, whereas a roll of 1 always hits and bypasses all armor. So even though it's centered on the d20, the feel is quite different.
I already mentioned a bit about genre, and I think it has an enormous impact on how satisfying the different levels of granularity and forms of dice usage are. Let's say you were playing a game all about wonder, enchantment, and magic, and maybe marketed to a young crowd. Having a lot of different highly colorful custom dice to use would really enhance the imagery. Say the dice are really visually attractive and color coded based on size, and when you cast a spell you roll a combination of different dice based on the type of effect (which you can spontaneously create on the spot). You grab the red (d8) for a damaging effect, the blue (d12) for a defensive effect, the yellow (d4) for a mental effect, etc. Or, in a narrative horror game you might want low numbers, and having larger dice to use is bad for you. You only get one to roll, and you want that one to be as small as possible. Maybe even color code it so the larger die sizes are progressively darker shades of grey (or other appropriate colors).
I've toyed with ideas like this, but I never put forth the effort to make them work (and I don't know any of the games I design would really benefit from them). But definitely, these ideas are brilliant when they're done right. Look at how Heroquest (or the later Heroscape) used dice with skulls and shields - it's one of the best dice systems around, and when you get down to it they're only a bunch of d6's.
Anyway Sword of Spirit, you should put your game (or bits of it) up on the House Rules section so we can take a better look at it.
Does make me wonder about the "buckets of dice systems" where you roll several dice and compare them all with a target number or use some other method to get a result. Shadowrun, original Storyteller System, HERO system, Wordplay, Cortex (to some degree). Their are some systems where you can be rolling up to 40 dice at times, yet people still seem to enjoy them.
Is d% at least better than these? Or because they use some other mechanic that isn't just the "false precision" d% give they get a pass?
No need for scare quotes; false precision is real concept. Look:
http://en.wikipedia.org/wiki/False_precision
Anyway, whether or not you run into false precision depends on the granularity, not the number of dice. It may be tedius to throw, say, 20 dice, but the tedium is a separate issue. So long as each die is only treated as a success or failure, then your granularity the same as for a d20 system. On the other hand, if those dice are read as numbers and then all added up, then your granularity can be quite high.
How would you do experience progression if you switched CoC to d20? In the d% system it only goes up by 1d6 at a time, so usually less than 5, so smaller than you can measure on a d20.
I played a Lovecraft game with a 2d6 system which (coincidentally) used a skill progression mechanic rather similar to Call of Cthulhu:
Every time you rolled a critical or a tie, put a check mark by your skill. Then after the session, make a skill check; if you
fail, improve the skill by 1. This meant that skills improved more and more slowly as you mastered them, and gave a good rate of progression overall.
To give you an idea of how effective this was, after using this system a few times for various different genres, none of my players ever agreed to play regular Cthulhu, D&D, or
any other published game system ever again, despite my occasionally suggesting a change for variety! This doesn't mean that the experience system specifically was better than Chaosism's, or even that the system as a whole was better. But clearly it did work.