I would expect many of your graphs to not have distinct eigenvalues.
Here's one reason: They have a very large number of degree $1$ vertices. Enough, in fact, that there will probably be a decent number of degree $1$ vertices which share a common neighbor with another degree $1$ vertex. These will give rise to many independent vectors in the nullspace of your matrix, so $0$ will be a multiple eigenvalue.
More generally, you can imagine the following situation: We say a subgraph $G'$ "dangles" from a vertex $v$ if the only edge connecting $G'$ to the remainder of the graph goes from some vertex $w \in G'$ to $v$. If you have two copies of $G'$ dangling from the same $v$ in the same way ($w$ occupies the same position in both graphs), then all the eigenvalues of $G'$ appear in the spectrum of $G$: The eigenvector is equal to $x$ on one copy of $G'$, $-x$ on the other copy, and $0$ elsewhere in the graph, where $x$ is an eigenvector of $G'$.
You can check, for example, that if instead of a power law graph you had the Erdős-Rényi graph $G(n,c/n)$ for fixed $c$, then every tree $T$ of fixed size appears as a dangling subgraph $c'n$ times (where $c'$ is positive and depends on the tree and $c$). This in turn implies there will be on average $c''n$ vertices having two copies of $T$ dangling from them, and for every such vertex you'll get a copy of all the eigenvalues of $T$. You might expect a similar phenomenon to happen with power law graphs, though I haven't checked this. (I did check a couple of graphs from the Stanford collection to see if they had $0$ as a multiple eigenvalue, and the ones I checked had it many times over).
This is all dependent on there being a sizable number of degree one vertices though. If we move to, say, random Erdős-Rényi graphs with edge probability $1/2$, I would expect the eigenvalues to be distinct with high probability, though as far as I know proving this is still an open problem (EDIT: This was recently proved by Tao and Vu -- their preprint is here and is described in this blog post of Tao's).
For more on this issue, albeit for random preferential attachment trees instead of graphs, check out the recent paper Spectra of Large Random Trees by Bhamidi, Evans, and Sen.
Best Answer
Surprisingly, the answer is 7 vertices for all 4-vertex subgraphs and 9 vertices for all 5-vertex subgraphs. I checked all graphs with 8 vertices and this was the first one (and only one so far) with 9 vertices that I found:
This is the listing of each of the 21 different subgraphs with 5 vertices:
This is a graph which contains all the graphs with 4 vertices:
That is, $K_4 : \{a,b,c,d\}$, $K_4-edge : \{ a,b,c,e \}$, $C_4 : \{a,b,e,f \}$, $P_4 : \{ c,d,e,f \}$, $K_{1,3} : \{b,e,f,g\}$ and the final one $\{b,c,d,f\}$.
And this is a graph with 10 vertices which contains all connected graphs with 5 vertices:
This is all of the different subgraphs of the latter graph:
I'll continue the search for a 9 vertex graph overnight, but I'm now doubting it can exist. I can also update my answer with the Maple code if anyone is interested.
Even with the exponential increase in number of small subgraphs, there are so many graphs that I'd like to believe that there would be a graph with all subgraphs on $k$ vertices which isn't exponential in $k$.(but I would be wrong!)