What is the scheme of fonts naming in PDFs generated by LaTeX and other software?

I have no idea about question (2) but this is relevant to question (1) and too long for a comment, I think:

According to the PDF spec from Adobe (section 9.6.4):

For a font subset, the PostScript name of the font—the value of the font’s BaseFont entry and the font descriptor’s FontName entry— shall begin with a tag followed by a plus sign (+). The tag shall consist of exactly six uppercase letters; the choice of letters is arbitrary, but different subsets in the same PDF file shall have different tags.

EXAMPLE EOODIA+Poetica is the name of a subset of Poetica®, a Type 1 font.

So what you are seeing is due to the embedding of subsets. Note that TimesNewRoman does not have the prefix because it is not embedded but is rather using a system font. (If you did not have this font installed, your PDF viewer would show an alternative value for Actual Font and/or Actual Font Type depending on what you did have available and how substitutions are configured on your system.)

The prefixes indicate – as @cfr has already pointed out in the comments (and also in her almost synchronous answer) – that the respective font is embedded only as a subset, ie. that only those glyphs are included that are actually used in the document. These prefixes are meant to prevent clashes between different subsets of the same font, and to allow merging them.

The standard that the PDF-producing application has to follow is Adobe's PDF spec, which says (in section 9.6.4, PDF 1.7):

For a font subset, the PostScript name of the font—the value of the font’s BaseFont entry and the font descriptor’s FontName entry— shall begin with a tag followed by a plus sign (+). The tag shall consist of exactly six uppercase letters; the choice of letters is arbitrary, but different subsets in the same PDF file shall have different tags.

The naming scheme is hard-coded in pdftex, so there is no way to change the font names, other than editing the PDF file itself, which is always quite risky. Also, many viewers (among them, Adobe Reader) will not display the prefix at all.

A final remark regarding microtype, as @cfr brought it up: In contrast to the prefix with subsetting, font expansion lead to having a suffix added to the name of the font which was indeed included multiple times with earlier versions of pdftex. However, this is no longer the case (since pdftex version 1.20), and the size increase of the PDF file with enabled font expansion is negligible.