I just noticed it for the first time when I watched the re-release. I tried looking it up and I've heard it called "worrt," "sevorrt," and "frog-dog." (I'm pretty sure its a worrt, but I'm not sure. A frog-dog is seen shortly before inside Jabba's palace near the Rancor pit trap door, if I'm not mistaken).Was it in the original film, and did it just get some CGI edits to make it more noticeable, or was it added later? If so, this looks like a prelude to Jar Jar. Could someone also tell me exactly what it is?
It was in the original
As you said, this is a worrt.
Worrts are brown, chuba-like creatures with toothy mouths that made their home in the desert wastelands of Tatooine. They would use their long tongues to capture unsuspecting prey as it passed, mostly insects and rodents. Perhaps the most notable worrt in the galaxy lived on the road to Jabba’s Palace in the Dune Sea.
It was in the original, and was not CGI. According to the Star Wars Databank:
The worrt was a puppet, like many of the creatures seen at Jabba's palace in Return of the Jedi. Its production nickname is simply "road creature."
Here's a picture of the worrt puppet, from someone who seems to have attended a prop show.