Программировать на чистых сокетах дело достаточно трудоемкое. Кроме того, что вам приходится работать на достаточно низком уровне, для обеспечения их неблокирующей работы(например при ожидании данных от другого клиента) надо использовать или потоки или poll/select.
Хорошим выходом может стать использования обертки, например из Qt. Так вы получите кросплатформенный код с меньшими затратами. Стоит также взглянуть на более высокоуровневые варианты, например ZeroMQ (не знаю как у них с p2p, но для общения между 2 клиентами это может упростить жизнь).
В простейшем случае для уведомления о своем присутствии клиент рассылает broadcast udp пакеты с информацией о себе. Основная проблема такого подхода, что такие пакеты будут зарезаны ближайшим маршрутизатором (наивно полагать что нам дадут разослать пакет каждому пользователю интернета). Поэтому такой подход работает только в простой локальной сети. Bittorent
умеет хранить информацию децентрализовано, но для первоначального подключения необходимо знать адрес хотя бы одного подключенного участника.
После того как вы знаете адрес другого клиента вы можете установить с ним непосредственное соединение. На самом деле тут тоже не все так просто. Если он находится за NAT, а до распространения ip-v6 для большинства(?) клиентов так оно и есть, то придется что-то придумывать. По этой теме можно поискать по запросу "p2p over NAT".
