The importance of medical data and the crucial nature of the decisions that are based on such data, as well as the large increase in its volume, has encouraged researchers to develop feature selection (FS)-based approaches to identify the most relevant data for specific medical problems In this paper, two intelligent wrapper FS approaches based on a new metaheuristic algorithm named the coronavirus herd immunity optimizer (CHIO) were applied with and without the incorporation of a greedy crossover (GC) operator strategy to enhance exploration of the search space by CHIO. The two proposed approaches, CHIO and CHIO-GC, were evaluated using 23 medical benchmark datasets and a real-world COVID-19 dataset. The experimental results indicated that CHIO-GC outperformed CHIO in terms of search capability, as reflected in classification accuracy, selection size, F-measure, standard deviation and convergence speed. The GC operator was able to enhance the balance between exploration and exploitation of the CHIO in the search and correct suboptimal solutions for faster convergence. The proposed CHIO-GC was also compared with two previous wrapper FS approaches, namely, binary moth flame optimization with Lévy flight (LBMFO_V3) and the hyper learning binary dragonfly algorithm (HLBDA), as well as four filter methods namely, Chi-square, Relief, correlation-based feature selection and information gain. CHIO-GC surpassed LBMFO_V3 and the four filter methods with an accuracy rate of 0.79 on 23 medical benchmark datasets. CHIO-GC also surpassed HLBDA with an accuracy rate of 0.93 when applied to the COVID-19 dataset. These encouraging results were obtained by striking a sufficient balance between the two search phases of CHIO-GC during the hunt for correct solutions, which also increased the convergence rate. This was accomplished by integrating a greedy crossover technique into the CHIO algorithm to remedy the inferior solutions found during premature convergence and while locked into a local optimum search space.