There are a few good brands of hot dogs that get shipped to the panhandle of Florida. Ones I know of are Boars’s Head and Dietz & Watson. As of a year ago you could get Dietz and Watson in Pensacola at Four Winds:
http://www.gofourwinds.com/
Apple Market at 1021 Scenic Drive (AKA US 90) in Pensacola sold Boar’s Head. These are pretty close to the Connecticut dogs you mentioned. Tobin’s is now made by John Morell (part of Smithfield Foods), so you may find that same dog sold under another brand name.

All I can suggest is that you visit or call any gourmet shop or independent retail meat market in your area and inquire if they sell any northeast frankfurters. All the franks I mentioned are sold in sealed plastic packages, so if you are in Pensacola, put them in a cooler filled with ice and they will be perfect when you get them home.

There were also discussions in this forum about people getting large supermarkets to order brands like Thumann’s and Grote and Wiegel for them. Use the search function; put in terms such as florida and fla, and search in the Hot Dogs, Sausages, and Bratwursts forum