1824, "one of an imaginary corps of mounted sailors," hence "a person out of his element and unfit for his place" [Century Dictionary], from horse (n.) + marine (n.). However by 1878 the term was being used in fact in reference to cavalrymen pressed into marine service or seamen mounted as an improvised shore defense.
horsehair
horsehide
horseless
horseman
horsemanship
horse-marine
horse-meat
horse-play
horsepower
horse-race
horseradish