Thanks! The fact that the number of isomorphism classes increases with $p$ for fixed $n \geq 5$ doesn't necessarily rule out a p-independent description, as in Motivating Example 2 (where the number can increase, but there is still a uniform description over $\mathbb{Z}$). The examples of order $p^{10}$ are indeed interesting though - I'll have to look into those further.

@JohannesHahn: I am aware of the work on classification by (small) coclass. I am specifically interested in the classification by order, related to algorithms for group isomorphism. The hardest cases seem to be the p-groups groups of class 2, which are of maximal coclass.

@KarlSchwede: Do you know a reference to the fact that any non-normal variety can be gotten by this gluing construction?

Are you asking specifically about lower bounds on sorting, or about general lower bounds? If the latter, there are many questions on cstheory.stackexchange that answer your question...

Your general point is well-taken, but I don't see that your example has no finite-dimensional representations. Can't I take any invertible finite-dimensional matrix (take $k=\mathbb{C}$ here), then take its square root, then it's square root, etc. to get a representation of your example algebra?

@AllenKnutson: I thought of that, but couldn't quite get it to work. I think I agree with Peter Samuelson's guess, that all this leads to is an algebra $A$ such that $A \otimes A$ is an $A - A \otimes A$-bimodule that satisfies an associativity condition...

Isn't this just pushing the bump under the rug? That is, if one wants to know that there is one Weyl group associated to a given semisimple Lie group, then one has to show that the resulting groupoid is connected, which in this case is the same as showing that the maximal tori are all conjugate... right?

Can you be a bit more specific, e.g. as to the value(s) of N you're interested in, the size of $G_i$, and the nature of the function f? As you point out, the min number of $P_i$ is already $|G_1 \backslash S_N / G_2|$, which in general I would expect to be quite large as a function of $N$... Practially speaking, $S_{10}$ is storable in memory, but $S_{20}$ isn't, so "O(10)" isn't really specific enough. Also, the structure of $f$ could be helpful. e.g., if $f$ is a polynomial in the variables $x_{ij}$ where $x_{ij} = 1$ iff $\pi(i) = j$ and $x_{ij}=0$ otherwise, that might be useful...