What ideas would he have been influenced by, and what did he take into consideration (or gave him the spark to formulate) the concept of the Special Theory of Relativity?
I honestly thought this concept to be a little bizarre - was wondering how Einstein actually came up with it. Couldn't just have been by the virtue of the fact that he was Einstein, right?
No, it did not come out of the blue. Einstein was trying to solve a very specific problem that the physics community had been grappling with for some time.
The problem is demonstrated most clearly by the Michelson–Morley experiment of 1887. Specifically the experiment discovered evidence against ether theory, which postulated that there was a medium through which EM radiation propagated (like say pressure waves through air or surface waves across a pond). Ether theory further hypothesized the ether was in uniform motion, and therefore the Earth (which moves in a non-linear way) must move relative to the ether wind (theoretically it's possible for any point on the earth to not be in motion relative to the ether wind, but that can only occur at one point in time).
The experiment essentially demonstrated that the speed of light, traveling in perpendicular directions, at various times during the day, remained a constant. Theories needed to be developed which reconciled Maxwell's EM equations with the apparent constant speed of light under any inertial frame of reference.
Einstein adapted a space-time metric from his advisor, Hermann Minkowski, to develop special relativity, which offered a solution to this longstanding problem.