Hi.
I've only been caching for a couple of months, and I can understand what you mean. When alone, I'm worried that someone out of view is watching me or when there are people around they think I'm a weirdo, but I just get one with the hunt and try not to think about it. If anyone DOES come up to me and questions what i'm doing, then I politely tell them it's none of their business - as long as I'm not on private land. A security guard came and asked what I was looking for while I was searching for a micro in the City last week. I just told him I'd dropped my pen, and he walked off.
I also do a lot of caching with my girlfriend, and it is MUCH easier to do with 2 or more people. One can keep an eye out while the other searches, or cuddling etc can disguise a good feel around for micros.
Taking my dog out for a walk is very helpful. A person with a dog is a lot less likely to arouse any suspicions, in parks, streets, paths or fields etc, than a person on their own.
To help with your uneasy feelings in urban areas, I have a couple of suggestions: a map will make you look like a lost tourist; a small packed lunch will give you a reason to be sat in a particular place for a while, as will a newspaper, magazine or book.
And yes, I think the feeling of unease is part and parcel to a point - especially the feeling of triumph once you've retrieved then replaced a cache with people around you none the wiser.