The following is a first stab at this problem.
If you have a fixed base $b$, then one can generate change up to $b^k-1$ with $k(b-1)$ coins. For instance, in binary, one can generate change up to $\$1.27$ with single coins each of denomination $1, 2, 4, 8, 16, 32, 64$ cents. In ternary, one can generate change up to $\$2.42$ with two coins each of denomination $1, 3, 9, 27, 81$ cents. And so on.
In that sense, the most bang for the buck (as it were) can be determined by identifying, for any given amount $M-1$ and base $b$, the required number of "stages" $k = \lceil \log_b M \rceil$, and then minimizing the number of coins $N = k(b-1)$. That is, we minimize
$$
N = (b-1) \lceil \log_b M \rceil
$$
Note that this is something of an overestimate, since not all coins in the uppermost "stage" may be needed (for instance, for $\$1.00$ in ternary coins, we do not need two $81$-cent coins), but it will give us a general idea of the principles involved. Let us avoid the discrete niceties of $N$ and instead minimize
$$
N_0 = (b-1) \log_b M
$$
and then
$$
\frac{dN_0}{db} = \frac{(1-b+b \ln b) \ln M}{b (\ln b)^2}
$$
Since both $\ln M$ and $b (\ln b)^2$ are positive in the range in question, minimizing $N_0$ amounts to finding $1-b+b\ln b = 0$. But $1-b+b\ln b$ is also always positive, for $b > 1$, so our best bet (in discrete coins) is to choose the minimum $b$, which is $2$: We should use binary coins to minimize the number of coins needed to make change, for most amounts. The number of coins needed is then
$$
N = \lceil \lg M \rceil
$$
where $\lg$ is log to the base $2$. It would be an interesting exercise (which I will defer for the moment) to determine for which amounts other coin configurations outperform binary.
ETA: Returning to think about this again, I think it must be that no other combinations can ever outperform binary (in the sense of requiring fewer coins); they might require as many, but never fewer.
One way to see this is to consider the cases where $M-1 = 2^k$—that is, situations where we must make change for all amounts up to a power of $2$. That is where binary coins are at their least efficient, since they include the single coin of that uppermost power of $2$, for a total of $k+1$ coins. For instance, to make change for $16$ cents, we must include a $16$-cent coin.
In order to outperform that, however, we must somehow make change with some other configuration for all amounts up to $2^k$ using only $k$ coins. But the number of non-empty subsets of a set of $k$ coins is only $2^k-1$. Therefore, there aren't enough selections of coins to make change in a way that is better than binary coins, so binary coins are always (among) the best.
Therefore, the answers to the first two questions are:
1. Coins of $1, 2, 4, 8, 16, 32, 64$ cents (seven in all) suffice to make change for any amount up to $\$1.27$, as noted above.
2. Nine coins, in binary configuration, suffice to make change for any amount up to $\$5.11$.
The generating function for distinct partitions into $k$ parts using elements from the set $\{1,\ldots,m\}$ is given using the $q$-binomial coefficient
$$\binom{m}{k}_q=\prod_{j=1}^{k}\frac{1-q^{m+1-j}}{1-q^j}\, .$$
The desired generating function is simply:
$$q^{\binom{k+1}{2}}\binom{m}{k}_q=\sum_{n=\binom{k+1}{2}}^{\binom{k+1}{2}+mk}p_{n,k,m}^*q^n\, ,$$
where $p_{n,k,m}^*$ is the number of partitions of $n$ in to $k$ distinct parts with no part greater than $m$.
We can use, for example, the free open source computer algebra system sage to expand
$$q^{\binom{6}{2}}\binom{10}{5}_q $$
which lists, as it's coefficients, partitions into distinct parts with $k=5$ parts and no part greater than $m=10$. Using the sage input:
j=var('j')
f(x)=x^15*product((1-x^(11-j))/(1-x^j),j,1,5)
show(expand(f(x)))
we get output:
$$\begin{align}&x^{40} + x^{39} + 2 \, x^{38} + 3 \, x^{37} + 5 \, x^{36} + 7 \, x^{35} + 9 \, x^{34} + 11 \, x^{33} + 14 \, x^{32} + 16 \, x^{31} + 18 \, x^{30}\\& + 19 \, x^{29} + 20 \, x^{28} + 20 \, x^{27} + 19 \, x^{26} + 18 \, x^{25} + 16 \, x^{24} + 14 \, x^{23} + 11 \, x^{22} + 9 \, x^{21} +\\& 7 \, x^{20} + 5 \, x^{19} + 3 \, x^{18} + 2 \, x^{17} + x^{16} + x^{15}\end{align}$$
Here we have 1 such partition for each of 15 and 16, 2 such partitions of 17, 3 partitions of 18 and so on.
The show command allows us to retrieve the output in $\LaTeX$ format so that, for example, it can be used to illustrate an answer on MSE ;)
By the way: A composition is different from a partition. For a composition the order of it's summands counts, whereas for partitions it doesn't.
Perhaps you already know this, however I am just making it clear for any other readers who may not be aware of the distinction. Of course, since we are counting partitions in to $k$ distinct parts then the number of compositions can be counted by multiplying by $k!$.
As per @GCab's request (see comments) I am posting a download link for more information on $q$-binomial coefficients:
A Course in Enumeration by Martin Aigner (pdf download)
The relevant section is 1.6.
Aigner gives a lucid account of the connection between $q$-binomial coefficients, lattice paths and restricted partitions. He then goes on to link, via a well known bijection, to the restricted partitions into distinct parts (corollary 1.2) talked about here.
Best Answer
I'm slightly confused by your wording, as you're looking for unordered partitions but then complain that the generating function doesn't “keep track of the orderings”. If I understand correctly what you're looking for, you can use the generating function
$$ f(q,u)=\prod_i\left(1-uq^{n_i}\right)^{-1}\;. $$
The coefficient of $u^kq^n$ is the number of ways to make change for $n$ with $k$ coins of the given denominations.