I think I figured it out.
First let's discuss the Catalan number recurrence. To obtain the formula for $C_{n+1}$ counting the number of correct strings of $n+1$ pairs of parentheses, we highlight the last external parentheses pair in such string and consider the parentheses strings $s_1$ before that pair and $s_2$ inside it: $s_1(s_2)$.
Any nonempty correct parentheses string can be uniquely decomposed into $s_1$ and $s_2$, and we can unambiguously restore $s_1(s_2)$ from any two (possibly empty) correct strings $s_1$ and $s_2$. Note that $s_1$ and $s_2$ are independent in the sense that no relation between them is required except for containing $n$ parentheses pairs in total. So we denote the number of parentheses pairs in $s_2$ as $k$, go through all possible values of $k$, and get the recurrence $
C_{n+1} = \sum_{k=0}^n C_kC_{n-k}
$.
Now regarding the multisets of graphs (or, more generally, multisets of nonisomorphic structures on $n$-sets). In a multiset, we can naturally group graphs by their number of vertices $i$ (and order these groups by size), and within graphs of the same number of vertices we can also group isomorphic graphs together and enumerate these groups somehow (introducing index $j$ for a given $i$; there are $a_i$ such groups, some of them possibly empty). Isomorphic graphs within each group can also be enumerated and ordered somehow.
Although the graphs are now ordered within any multiset, we cannot do what we did with parentheses strings and split the multiset into two independent parts (two multisets or maybe a multiset and a graph): even if we highlight, say, the last graph, or the last group of isomorphic graphs, or the last group of graphs with the same number of vertices, in any of these cases it would impose serious restrictions on the non-highlighted part. It spoils the independence of the parts and ruins the approach "count ways to construct each of the parts separately, multiply, and sum over the size of one part".
We'll do another way. In a nonempty multiset of graphs, pick one of the $n$ vertices. Set a rule that the whole graph containing that vertex is highlighted, together with graphs isomorphic to it coming after it (they are ordered, remember?). So we have split the multiset into two parts: the residual non-highlighted part, which is a (possibly empty) multiset of graphs, an the highlighted part, which is a block of some nonzero number of isomorphic graphs (on $i$ vertices, of $j$th kind). Denote the total number of vertices in the block as $k$.
For example, here we have a forest, in which the trees are ordered, and a vertex is picked, which determines the highlighted block of isomorphic trees starting from the one with the picked vertex and others to the right of it:
Note that we can unambiguously restore the original multiset from the residual multiset and the block, and it works for any residual multiset and any block, the only restriction is that the total number of vertices should be $n$. (Just like with Catalan numbers! However, now we need to learn how to count blocks.) On the other hand, any pair consisting of a residual multiset and a block of isomorphic graphs (with $n$ vertices total) can be obtained from some original $n$-vertex multiset in exactly $i$ ways (the number of vertices in a graph from the block). Therefore, if we go through all possible pairs of a multiset and a block with $n$ vertices total and count them with the weight $i$ (determined by the block), then we'll get exactly the number of ways to take an $n$-vertex multiset, order its vertices, and pick a vertex in it, which equals $nb_n$.
So for fixed $k$, $i$, and $j$, the block is determined unambiguously (although it only exists if $i|k$), while the residual multiset can be chosen in $b_{n-k}$ ways. Multiply by the weight factor $i$; sum over $j$ (since the summand does not depend on $j$, this only adds the factor $a_i$); sum over the allowed values of $i$ (i. e. the divisors of $k$; $b_{n-k}$ factors out of this sum); finally, sum over $k$ and divide by $n$ to get $b_n$. After replacement $i\to d$ we get the desired formula from the question.
Updates
