Your (perhaps understandable) confusion derives from your mistaken partitioning of the phrase. The NP 'what color eyes' consists of a head noun 'eyes' modified by the NP 'what color' (consisting, in itself, in a combination of the noun 'color' and interrogative determiner 'what'). Although once extant, *What color of NP is no longer acceptable in contemporary usage.
With other similarly constructed phrases, however, the option to insert the preposition is still available. Both what flavo(u)r NP and what flavo(u)r of NP are acceptable, although the former is somewhat more common.
Student or Learner