Baron’s question deals with two quite different issues: what should be considered to be the iconic warship and what kind of warship the average person would be sure to identify accurately. I’m not sure that there’s any particular kind of warship that the average person would be sure to identify accurately, and keep in mind that the example Baron gave – 19-year-old-girls – is too specific (at least in my opinion) to fit the broad concept of the average person. A submarine probably would have the highest recognition factor because its defining characteristic (its ability to dive underwater) gives it such a unique shape and because its diving abilities can be considered separately from the specifics of its precise military role (ballistic missile sub, attack sub, etc.). On the other hand, the warship with the lowest recognition factor – or to put it another way, the ship whose definition is the most potentially confusing – is pretty clear in my opinion: the battleship. To the general public (or to use Calvin’s phrase, “To the untutored eye of the ignorant layman”), the word “battleship” means the same thing as “combat vessel” and therefore is a generic term for “warship.” That’s not what “battleship” actually means…but in fairness, even naval experts get into arguments over what a battleship is and where the distinction lies between a battleship and a battlecruiser (as in the case of the WWII German vessels Scharnhorst and Gneisenau).
As for what “the iconic” warship is, the answer is: take your pick. Or rather, choose your era and then take your pick. In the age of oars, the iconic warship was (in my opinion) the Greek trireme. Three-decked first-raters like HMS Victory would be a good choice as the iconic ships of the age of sail. For the WWII era, my personal favourite would be fast battleships, which simultaneously reached the peak of their evolution and became obsolete at that time…but that’s just my preference.