John Conway writes:
Let me ask for the smallest group in which two squares can multiply to a non-square....
It's nice to see this. I was going to look with Gap, and your analysis helped convince me.
Therefore, the smallest groups in which squares can multiply to a non-square are A4 and Q12; indeed, they are the only such groups with order < 16 (and probably the only ones with order < 20, since I don't believe there will be any of order 16).
I found two such groups of order 16, but I haven't figured out what their names are. A presentation for the first is <a,b : a^2 = b^4 = (b a b)^2 = (b^-1 a b a)^2 = 1> . Its squares are 1, b^2, and (a b)^2, and the product of the last two is not a square. The other group may be presented <a,b : a^4 = b^4 = a b a^-1 b = 1>. Its squares are 1, a^2, b^2, and again the product of the two non-identity squares is not a square.
A much harder and more interesting problem is: what's the largest probability we can attain?
The largest among groups up to order 255 is 5/6, in a 192-element group. Gap calls it SmallGroup([192,1022]), but again I don't know a name for it. The smallest presentation I've found is <a,b,c : a^3 = b^4 = c^4 = [b,c] = [a,b^2] = [a,c^2] = (a c)^3 = (a b)^3 = [c,a^-1 b^-1 a] = 1> where [x,y] means x y x^-1 y^-1. This is edged out by probability 27/32, in SmallGroup([384,572]), which I haven't looked at in detail. Dan