I've done all that too - gone on holiday alone etc. I don't have a problem eating in restaurants on my own, except for talking to the waiters! I think I isolated myself at high school, thinking myself unworthy of other people's companionship, but then didn't learn all the social skills.

Things improved but I still need time-out from people. I figure it's a balance between pushing yourself to be with people and feeling the discomfort to greater or lesser degrees, and being on your own - sometimes good, sometimes distressing. I can see it would just be annoying going out with selfish people.

I do recommend group therapy for learning how to be with people. A year ago a guy in my group couldn't handle an extended social situation. This year the same thing went really well and he joined in everything. Most of the things we go over in the group are just letting people know they are socially acceptable and OK to be with, and trying to work out how to worry less about each and every social interaction. In our heads it's all going horribly wrong, but from the outside there often isn't anything wrong. You can actually ask people how you come across.

As to finding people you click with, I don't know. I was isolated at work until I found someone else who was fairly new in a different department, and until the nasty people I was working with left, and the really friendly new ones arrived. Everyone else was already settled in their lives.

Common interests is the thing that always comes up! Evening classes, sports, local support groups?