(As a warning, I got slightly jargony in this post. SR = special relativity GR = general relativity c = speed of light EM = electromagetism B-field = magnetic field)

First off, SR probably would have been developed within a few years of Einstein's publication. This is because the root problem that Einstein was trying to address using SR was actually very well known to the physics community at the turn of the last century, and had to do with the behavior of Maxwell's Equations near the speed of light. Maxwell's Equations are the set of four equations that completely describe electromagnetic interactions and wave propagation in free space, and are one of the intellectual triumphs of physics (SR/GR being one of the others).

The problem facing physicists around 1900 was that Maxwell's Equations begin to break as you approach the speed of light. Specifically, an observer traveling at a substantial fraction of c with some EM system in front of them (at the same velocity) would see completely different system properties than a stationary observer watching the same system. As one example, the stationary observer would see an electric current in the system (due to the system's velocity), which would generate a magnetic field, but the traveling observer would see a set of stationary charges and hence no B-field. The is physically impossible, so people recognized that something was wrong somewhere.

The initial solution was created by Hendrik Lorentz, who devised a set of frame transformations, now known as the "Lorentz" transformations, that allowed Maxwell's Equations to act correctly near the speed of light. These are in contrast to the Galilean transformations that govern our day-to-day lives, and which were being applied previously.

So that's the background. The crucial insight that Einstein had that led him to SR was the physical interpretation of the transformations. Namely, that they implied that the speed of light is the same for all observers, the speed of light is a sort of universal speed limit, and that the laws of physics are the same in all inertial (non-accelerated) reference frames. Since the Lorentz transformations also change the relative passage of time between two reference frames traveling at two different velocities, Einstein also realized that the "distance" between two events needed to be described using a single "spacetime" distance, rather than separate distances in space and in time. That got him to treating space and time as a single 4-dimensional construct.

The experimental, theoretical, and mathematical basis for SR were thus all pretty well established when Einstein came along. All he needed to do was to assemble all of the disparate pieces and assemble them into a unified system of thought. So it seems very reasonable to suppose that if Einstein had not developed SR in 1905, some one else would have gotten there within a few years.

(N.B. - I say "all he had to do," but that in no way is meant to trivialize what Einstein accomplished. As was demonstrated 20 years later in the development of Quantum Mechanics, the experiments and the math are often the relatively easy bits. It's figuring out what it all actually means that is hard.)

Once you have SR developed, getting to GR is the next logical step. Recall that SR deals with inertial (non-accelerating) reference frames. GR is the extension of SR to also account for accelerating frames (both via gravity and via something like rockets). This makes GR considerably more complicated than SR, but the basic ideas behind it, or at least the idea that you need to figure it out, are all in place once you've got SR worked out.

Once major practical difference in GR that would probably arise of Einstein had never existed is the notation used to do the calculations and display the results. Einstein actually invented his own new mathematical notation to help with GR calculations, and this is now known as "Einstein" notation. It allows one to compactly write out and work with linear algebra operations.

Without Einstein, it seems reasonable that this specific notation would not have been developed. Insofar as a notation system influences how we think about what we're working with, this would have then changed how people dealt with and interpreted the results of alternate-GR. A nice example of what I mean here would be to look at the different views of Calculus coming from Leibniz's and Newton's notation for the same problems.

Source: I have a PhD in astrophysics.