Non sequitur is latin for “it does not follow.” It’s in latin because it is a rhetorical device, and rhetorical devices were exhaustively studied in the Classical and Renaissance worlds. To “not follow” is to be completely unrelated to the flow or logical path of a discussion or argument.
A “red herring” is a misleading piece of information. In the 1800’s, british prisoners used to rub herrings on their escape paths to divert the attention of pursuing dogs. In the 1920’s, the U.S. investment community began using the term “red herring” to describe investment reports that were not complete, and therefore potentially misleading. The current meaning evolved over time to include any clue or piece of information that might trick someone into following the wrong line of thinking.