What would be the equation of the parabola that one would rotate to form the appropriate paraboloid if it were to be designed to set fire to a ship 100m from the mirror?

A paraboloid mirror of that size would challenge modern telescope makers. Archimedes could have got just about as good an effect with a large number of small flat mirrors, each individually trained on the ship. (Somebody - Arthur C Clarke, I think - had a short story in which a football referee was vaporized by a stadium full of fans armed with reflective souvenir programs...)

If it was a parabola, the distance depends on the elevation of the sun above the horizon. The focal length of a paraboloid with formula $z = a(x^2+y^2)$ is $\large \frac{1}{4a}$; but this is only the distance from the mirror to the ship if the sun, ship, and mirror are in a straight line. If the sun were overhead then the mirror would be a slab from the side of the paraboloid and the distance would be greater (twice as great).

How large would the burning mirror need to be?

That depends on what exactly the mirror is to do: dazzle the man at the tiller, threaten him with blinding or burns, set the sail on fire, or set the hull on fire. This has, as I recall, had the wheels studied off it by the good folks at "Mythbusters."

What is the likelihood that this story is true?

I would say that the antipersonnel level is perfectly plausible. In a Mediterranean summer, the sun is pretty bright, and even a dozen hmeter-square mirrors all directed at one man would be pretty effective - and frightening, especially in a culture where the boundary between the natural and the supernatural was not well understood, and even more so given the reputation of Archimedes.

I think it more likely that that is what happened and the tale grew in the telling - but then, I wasn't there.

Good hunting!
RD