With the free immigration records at Ancstry.com, I have been searching for all my known and suspected travellers, and I found a Charles E. Kidd, aged 26 sailing into New York in October 1896....with Mrs Kidd aged 21!

Hmmm..and if that Mrs Kidd wasn't Mary, then maybe he ran away with someone, at least at the start. Oh I wish I had a time machine sometimes!
Below them in the manifest is a Thomas Kidd and his wife, but I can't find a connection to him as yet.
Nina