East Iceland : Seyðisfjörður
There is a weekly ferry run by Smyril line  from the Faroe Islands (duration: 1-2 days) and to Hirtshals, Denmark (3-4 days). The ferry departs once per week on Tuesday 8pm during the low season (April-June and August-October), and on Thursday 10am during high season (June-August). A return journey to Denmark for instance will set you back €280-590 with a car or €120-250 per passenger, depending on the season, excluding a supplement fare for a cabin or bed. Remember to book in advance, as prices vary a lot.
The nearest Airport in Egilsstaðir, about 30 minutes away, has regular flights to the capital. There are several buses a day to Seyðisfjörður connecting with the flights stopping in central Egilsstaðir on route. From central Egilsstaðir there are one or two additional departures per day during the summer, as well as the option to change to several bus lines connecting to other parts of Iceland. The buses are run by Ferðaþjónusta Austurlands (tel.: 472 1515) which has no website, but the city administration website  maintains a an updated schedule.