[gigafemtonano]

I'm pretty sure that Einstein intuitively "guessed" that the speed of light would be the fastest possible speed and used that fact to work out the rest of the equations. E = mc^2 was the bizarre discovery that those equations yielded, and it was so weird that he felt like he had made a mistake at first.

[splat]

That's not quite right. Einstein (and several other physicists of the time) inferred that the speed of light might be invariant in all reference frames from the structure of the Maxwell Equations where the speed of light enters as a true, fundamental physical constant of the universe.

[gigafemtonano]

From the actual paper: http://www.fourmilab.ch/etexts/einstein/specrel/www/

We will raise this conjecture (the purport of which will hereafter be called the "Principle of Relativity") to the status of a postulate, and also introduce another postulate, which is only apparently irreconcilable with the former, namely, that light is always propagated in empty space with a definite velocity c which is independent of the state of motion of the emitting body. These two postulates suffice for the attainment of a simple and consistent theory of the electrodynamics of moving bodies based on Maxwell's theory for stationary bodies.