Rock Giants are big and hardy, so it is advised not mess with them. Since their skin is so thick it is not smart to try a direct confrontation. Instead, a smart mix of minions (greens are a great candidate to use here) can destroy a rock giant.
The first Rock Giant is found near the Glittering mine in Golden Hills. It must be slain in order to gain access to the mine. Also the Rock Giants are one of the monsters that will spawn in the dungeon. In this case there will be five of them at once.
At the end of the Skull Canyon you will find a imprisoned Rock Giant. After you have freed him, he will kill all the Bandits in the area. But then you need to kill him with your minions, so that he forms a bridge to the gate.