The Starcraft Tilesets... how did they do the artwork for these? Let alone how they made 1 32x32 be able to tile next to several DIFFERENT tiles... This has probably been on the board before, but nothing I have seen.

Their tiles can''t be "over many other tiles". For that you use what could be called "border tiles". Little partial tiles that serve as translations between, say, water and mud.

water tile ... mud tile
becomes

water tile ... mud tile with a beach tile on top of it