Supposedly "with a grain of salt" comes from Pliny the Elder, Natural History 23.149, where he tells of an antidote to poison which included a grain of salt (discovered by Pompey among the papers of Mithridates, and supposedly written by Mithridates himself...of course Mithridates is famous for having acquired immunity to various poisons).
In Pliny it reads addito salis grano but the formula cum grano salis is better known.