I'm not shy, but this is definitely something I have a problem with. I generally just don't know what to say to a complete stranger. Going up to them and talking about, well, nothing just seems beyond orders of magnatude in rudeness. I feel almost as strongly that way as I do that holding eye contact is a serious form of personal violation. I know they're not true, but that's how it feels.
Now, if there's something "valid" to talk about, that's a whole 'nother ball game. Unfortunately, when you're dealing with complete strangers, you don't know enough about them to have an interesting conversation. Whether you see a woman at a coffee shop, bookstore, park trail, etc., other than the fact that you find her physically attractive (I'm assuming you do), you really don't know anymore about her than that and that subject is not one you talk about.