Mobile map landmark symbols are pivotal in conveying spatial semantics and enhancing users’ perception of digital maps. This study employs a three-factor hybrid experimental design to investigate the effects of different landmark symbol types and their color associations with annotations on search performance using eye tracking methods. Utilizing the Tobii X2-60 eye tracker, 40 participants engaged in a visual search task across three symbol types (icons, indexes, and symbols) and two color conditions (consistent and inconsistent). This study also examines the impact of gender on search performance. The results indicate that INDEX, emphasizing the landmarks’ functions and key features, most effectively improve search accuracy and efficiency while demanding the least cognitive effort. In contrast, SYMBOL type characters, with clear semantics and minimal information, require less visual attention, facilitating faster preliminary processing. Additionally, cognitive style differences between genders affect these symbols’ effectiveness in visual searches. A careful selection of symbol types and color combinations can significantly enhance user interaction with mobile maps.