When you first explore the battle frontier, go to the BATTLE PALACE, and go to the southwest corner. SURF to the other side, and you will first see a little old lady.
continue down the path south of the lady until you notice a strange tree that moves when you press A.
This is a sudowoodo, origianlly found in the GSC versions.
To battle it, use the WAILMER PAIL on it. You have only one chance to catch it, so don't screw it up.
After that, you can SURF on the water that the Sudowoodo was blocking. SURF down the WATERFALL, and keep surfing left (there are no fish or anything in the water, so don't bother.)
After a while, you will surf to a cave known as the ARTISTAN CAVE. Go inside, and as you explore the cave, you will find many stat items in the boulders (carbos, etc.) The only pokemon in this cave is SMEARGLE. (hence, the ARTISTAN cave.) The SMEARGLE are generally level 41 to 50. They can only use sketch once before they start struggling.