You're right about not being able to turn it off. I didn't look to see if it was greyed out - like it is.
To boot into recovery, power down the phone. Then simultaneously press and hold the home button, volume up, and power. You can let go when you see the little blue message up top of the screen saying it's entering Recovery. Once it is in Recovery mode, look at the 4 options you have there and select the one to wipe the partition cache. Pay attention to what you are doing so you don't accidentally choose to wipe the device completely/factory reset. The wipe takes only a couple seconds and then you can reboot when it says it's done.
Btw, when you clear data in app manager, the first time you open gallery after that, it will need to re-populate your photos so just give it a minute to do that and don't worry about it being slow the very first time you open it after a clear data. After a clear data you will also need to go through your settings and make sure everything is set up the way you want again. This only applies to clearing data, not clearing cache, which will not reset any settings.
Besides making sure Picasa sync is not checked, look under "content to display" in the gallery options and make sure picasa is not checked there. Also uncheck anything else you don't need, like facebook, or any other options you have there. Of course if you want to display or sync something I'm not telling you not to do so. But the least it has to sync and the least it has to search for things to display, the faster things will be for you, so uncheck anything you don't want/need.
Also, are you saving your photos taken with the camera app to the SD card? This is just fine if so, and I do so with no problem. But if you continue to have a problem after the above is all done, temporarily change that to the phone storage and remove the SD card and see if you still have a problem. Filesystem problems or file corruption - easy to fix with a re-format of the card - can cause indexing problems that cause high cpu usage or SD card hardware problems can cause issues as well of course.