Deep neural networks (DNNs) have achieved impressive results in many fields. However, the use of black-box solutions based on DNNs in medical applications poses challenges, as understanding the rationale behind decisions is crucial for application in healthcare. For those reasons, we propose a new method for the evolutionary multi-objective design (MOD) of small and potentially explainable EEG (Electroencephalography) signal classifiers. We evaluate a combination of genetic algorithm (GA) for feature selection with multiple algorithms for the automated design of the classifier, including Support Vector Machine, k-Nearest Neighbors, and Naive Bayes. To further improve the classification quality and obtain less complex solutions, we compare three different MOD scenarios targeting the accuracy, specificity, sensitivity, and the number of used features. In addition, we evaluate the use of Cartesian Genetic Programming (CGP) as a way to achieve smaller and more interpretable solutions and combine it with the compositional co-evolution of selected features to improve computational requirements and find solutions in a reasonable time. The proposed methods are experimentally evaluated on tasks of alcohol use disorder and major depressive disorder classification. Experimental results show that newly proposed MOD scenarios lead to significantly better trade-offs between the accuracy and the number of features compared to the state-of-the-art method employing the NSGA-II algorithm. The proposed co-evolution of features (evolved by GA) and classifier (evolved by CGP) allowed the design of small and potentially explainable solutions and led to 20–100 times faster convergence than the baseline CGP-based approach.