First, please note that your expressions should include not, and that:
in (a) much is a pronoun and choice is a countable noun.
in (b) much is an adjective, but this time choice is an uncountable noun. (You cannot say *The countries did not have much choices - you would have to use many instead of much to be able to use choice as a countable noun in the plural).
To put it in more grammatical language:
In much choice, much functions as determiner with the noun as head of the NP; much here is restricted to occurrence with
non-count singular nouns. In much of a choice, much is fused determiner-head with an of phrase complement; the noun in that PP must be a count singular determined by a. (CaGEL p. 533 - I have introduced your examples in the quotation for simplification)
And yes, there is difference in meaning:
- not much choice merely negates quantity, there aren't many options
whereas
- not much of a choice emphasises that you have an option, but it isn't really freely chosen. Or the choice is poor.
not much is defined as:
a small amount of (something)
- There's not much food in the house. (M-W)
Not much of a emphasises quality rather:
If you describe something as not much of a particular type of thing, you mean that it is small or of poor quality. (Collins)
- It hasn't been much of a holiday.
CaGEL analyses this structure but with a different use, which the authors call Quantification of predicatives. Although it is a different instance, it is worth noting what they say about much of a + noun:
In Ed isn't [much of a husband], plain much, comparative more and less, and sufficiency enough are used as degree quantifiers
for properties expressed in predicative NPs. Husband doesn't usually denote a gradable property, but in this construction we understand the quantification to apply to the degree to which Ed has the properties that are taken to characterise a good husband. Syntactically, much is a determiner-head taking a PP complement in which of is followed
by an NP with the form a+ nominal. Much here is strongly non-affirmative. (p. 415)
Finally, note that not much of a choice is recorded as colloquial by some dictionaries. CaGEL says it is more likely to be found in spoken English, conversational contexts, informal style, or the usage of younger speakers, whereas not much choice can be said to be more characteristic of written
English, literary contexts, formal style, and the usage of older speakers. (p. 826)