Видите, Вы пишете (предполагаете), что воспринимаете любого мужчину как потенциального партнера, что и дает чувство стесненности. Как насчет попробовать изменить это восприятие? Там, где Вы общаетесь с мужчинами (работа? соседи? Мужья подруг?) обращайте больше внимания на то, как строятся Ваши отношения с теми, кто точно не будет Вашим партнером, поймите, что все мы люди независимо от пола, и с любым человеком нужно уметь общаться. А умения всегда приходят в процессе практики. Если таких мест, где Вы бы регулярно могли оттачивать свои навыки нет, то не могу не дать банальный совет записаться на айкидо или в турклуб или в йоговский клуб.... только не на фитнесс!).
Второе, на что хочу обратить внимание. наверняка Вы уже (не дожидаясь начала работы с психологом) копаетесь в своем прошлом, в детском травматичном опыте, вспоминаете и пытаетесь раскрутить этот клубок. Если это так, то не пожалейте средств, времени, найдите в себе решимость продолжить эту работу со специалистом. Человеку обязательно нужно проговорить свои проблемы вслух в присутствии другого. Тогда они начнут решаться.
Еще одна маленькая возможная зацепка, которую я вижу в Вашем ответе, так это слово "приятельницы". Вы пишете, что с женщинами отношения у Вас складываются прекрасно, но тут же пишете слово "приятельницы", а не "подруги". Нет ли у Вас общей проблемы боязни открыться, довериться другому человеку? Если эта версия отозвалась, то это еще одно направление, в котором можно поработать.