Which transliterated version of a surname sounds better, Potyomkin or Potemkin?

Yes, English routinely transliterates Cyrillic Ё as E. For that matter, Russian routinely writes Ё as Е. Our transliterations (and your default orthography) aren’t up to date with the last couple of centuries of sound change in Russian.

Potemkin is the most familiar version to English-speakers, since “Potemkin village” is a well known expression (and one they tend to have seen only in print). If they are somewhat educated, but do not speak Russian, they will actually be confused by Potyomkin.

So I’d go with the established, conventional Potemkin rather than the phonetically accurate Potyomkin, myself. But that’s not the modern trend in English; the modern trend is for phonetics over convention (e.g. Beijing not Peking). Not Moskva yet, though.