This post offers no help of substance; however, there are some bits of information and suggestions which may be useful.
Szent-Maria (Zemplen varmegye) is now in the Slovak Republic and is known as Svata Maria. Tornyosnemeti remains in Hungary and is situated on the E-71 route just shy of the Slovak Republic border. It is nne of Miskolc.
Frank Nagy = Nagy Ferenc or Feri (have seen FERENCZ) Joseph Nagy = Nagy Jozsef or Josef
You have not indicated what information you have been able to glean from the Ellis Island site. If you know the religious affiliation(s) of your subjects, the LDS Family History Library in Salt Lake City ought to be the next step in your quest.
In my own situation, I am blessed in living in a community which has a Family History Center at its LDS Church. For more than two years, I have been struggling to fill in the gaps in my knowledge about my ancestors. It is not an easy task, but neither is it an impossible one.