It was obvious to me for the following reasons:
1) Played by the same actor.
2) No change in facial makeup (the only difference between Sideous and Palpatine is that Sideous changes his voice slightly and has his eyes covered by the hood). When Sideous is seen from the side, his face looks EXACTLY like the Emperor's face in ROTJ when he is talking to Vader and the camera focuses on him in profile. The only change is that in ROTJ his chin is a little more wrinkled and pale.
3) In the Star Wars movie novelisation, they call him "Emperor Palpatine." Thus it's always been "Palpatine" that has been the official name of the Emperor. I didn't expect Lucas to change this major detail, even though it was never stated onscreen. Just like how the word "Sith" is never mentioned onscreen until Episode I. It's just one of those details that Star Wars fans always "knew."
4) Sideous makes constant references to "the Senate" as if he has control of it. Since Palpatine seems to be a manipulator and shrewd leader anyway, this makes perfect sense. Finally at the end of the film when Yoda and Windu are talking about "which was destroyed, the master or the apprentice" and the camera pans over to Palpatine and focuses right on his chin (the most visible part of Sideous's face when we see him).
5) And finally, they dress the same. Sideous in the shadows wears the cloak and broach thingy just like the Emperor does in the classic trilogy. When Palpatine is "deformed" he puts on the cloak though it's a slightly different than the one the Emperor wears in Episode VI. I don't recall if he has the broach thing on at that point in Episode III, though.
With the audio commentary for TPM being available in 2001, (iirc it was the Episode I commentary), Lucas comments on the DVD how he wanted people to recognize Darth Sideous by introducing him in a hologram, just like he introduced him in Empire Strikes Back. Emperor from ESB = Darth Sideous from TPM. (Unless I'm confused and he said this on the ESB commentary released in 2004, in reference to TPM, so somebody feel free to correct me).
Now beyond that in AOTC it's even more obvious, as more references are made to Sideous being on Coruscant and being happy about the war starting, etc.
Now the only "glitch" is that the Emperor in ROTJ has yellow and red "Sith eyes" (Darth Maul is the first person in Star Wars to demonstrate them to us after Palpatine) and prosthetics on his face to make him look ancient and Vampiric. He also has rotten teeth. Now we could have just imagined that he was a really old man and didn't take very good care of his health. The EU theorized that he used the Dark Side so much that his body decayed and aged faster than normal, forcing him to transfer his soul from one cloned body to the next.
In any case, we finally were shown absolutely that they were the same person all along in ROTS. Palpatine's face is disfigured by his own Force lightning somehow and we see his voice change back and forth between the Palpatine in TPM and the Emperor we know and love from ROTJ (and the cackle is now the same). His face is shown in profile when he first puts on his hood, and it looks just like the Emperor from ROTJ. They start referring to him as "Emperor." Vader starts calling him "My Master" or "My Lord." The transformation is complete!
But yes, I was 99.99% positive that Palpatine was always supposed to be the Emperor we saw later in the classic movies. Before I listened to the audio commentary I thought, well maybe 0.01% chance that Lucas will make them different people in some horribly contrived way just to throw everyone off and make a "big reveal" like Vader being Luke's father. I figure Lucas does this sort of thing, so it might happen. But then it was exactly what all these "they are clones of each other!" people EXPECTED, so it was extremely doubtful.
The only thing that to me was not "obvious" that a lot of people assumed, was that this "Darth Plagueis the Wise" was really Palpatine's master. Until I read the novelisation and the Visual Dictionary, I assumed he just made up the story in his ploy to trick Anakin into thinking the Sith had the answer to all his problems. It's sort of like how I assumed that Sifo-Dyas never really ordered the Clone Army in AOTC. It seemed obvious to me that Count Dooku simply assumed the identity of a dead guy and ordered the army in his name, with the Kaminoeans being none-the-wiser. Now it turns out that officially, Sifo-Dyas really did order the Clone Army, under the urging of Dooku, and then Dooku killed him (though Dooku recruited Jango Fett, under his Sith name Tyrannus as mentioned in the movie). That such a thing could happen to a "Prominent Member of the Jedi Council" without anybody knowing or figuring it out for 10+ years is pretty incredible.
Oh well... so much for subtlety!
Oh, I realized I forgot to directly address the opening post:
Was it always obvious that Palpatine was a Sith? No. Because when he was first introduced in the Star Wars novelisation (only mentioned in the movie) he was depicted merely as a scheming and corrupt politician. No indication that he had any force abilities whatsoever. We never saw him, he was merely a background figure mentioned a few times. Darth Vader was the only "Sith Lord" we knew of. Everybody thought so until Empire Strikes Back or possibly even Episode I (Star Wars: Behind the Magic
from 1998, for example repeated the line that there was only ever one Dark Lord of the Sith at a time, and that was Vader!).
As soon as Empire Strikes Back came out, it was obvious that he had the Force, since he talked about sensing the future and a disturbance in the Force, etc. Though the term "Sith" is never used, we assume he is powerful in the Force, and a Dark Side user, since that's what Vader is. Is he a former Jedi? We are never told, though in ROTJ he makes disparaging remarks about Jedi so we assume if he was ever a Jedi, he's not one now, yet ANH makes references to Darth Vader being part of the Jedi or a former Jedi (Obi-Wan refers to himself as being "once a Jedi, the same as your father").
I forget if the ROTJ novelisation actually refers to Palpatine as a "Sith." It may, it may not. The EU authors were forbidden to write about the Sith for many years before TPM, so they used the term "Dark Jedi" instead, though the term Sith Lord was always connected with Vader specifically. Then they had those Tales of the Jedi comics which came up with a history for the Sith.
I guess we could put two and two together and assume that if Palpatine was Vader's master and they both used the Dark Side, they both must be Sith Lords. When Episode I comes out, it's clear that nobody ever thought Palpatine had the Force or was a Jedi (though he clearly had the Force in secret, never demonstrated in action until Episode III... though you'd think he must have used the Force to "cloud the perception" of the Jedi so they couldn't sense that this powerful being of the Dark Side was standing right there under their noses the whole time), so he wouldn't be a fallen Jedi.
Since he was the master of Maul, identified as a Sith, then it was clear from Episode I that he was a Sith. So he's always been a Sith, even if never stated onscreen, it makes sense from the other materials. Even if you just had Episodes V, VI and I, you could figure it out.