Почему бы не позволить пользователю выбрать, на каком порту он хочет разместить службу? Например, добавьте значение в файл конфигурации вашего приложения, которое передается в ServiceHost. Вы также можете попробовать случайным образом сгенерировать номер порта и проверить, открыт ли он, а затем повторить процесс, если его уже использует другое приложение.