In this paper, we investigate several relay selection strategies for cooperative Single-Carrier Frequency-Domain Equalization (SC-FDE) with the amplify-and-forward protocol. We consider both maximum likelihood (ML)-SC-FDE and minimum mean square error (MMSE)-SC-FDE receivers. We provide a novel pairwise error probability (PEP)-based selection criterion (SHARM) for frequency selective channels. We further present several selection strategies for cooperative (C) MMSE-SC-FDE receivers, which are motivated by minimizing the instantaneous error rate. These are, norm-based relay selection (NBRS), instantaneous mutual information-based relay selection (CBRS), singular value based relay selection (SVRS), and equalizer output signal quality-based relay selection (EQRS) strategies. We further propose a novel relay selection strategy, selective-to-flat fading relay selection (SFRS), in which from the effective frequency selective source-relay-destination channel link associated with the selected relay, only the channel tab with highest power is passed to the destination terminal. Additionally, to tackle the multiple relay selection problem considering generic mobile scenarios with moderately fast fading channels, in order to select the near best relay subset within the minimum processing time, we apply estimation of distribution algorithm (EDA) and formulate a modified EDA for the relay selection problem. Our results show promising performance of EDA with comparable computational complexity.