[noun] + をはじめ、[sentence] [noun] + をはじめとして、[sentence] [noun] + をはじめとする + [noun]
をはじめ goes after a noun and holds it up as the leading example of a larger group: "X and many others", "starting with X". The noun is the best-known or most important member, and the rest of the sentence names or sums up the group it heads. It belongs to formal speech and writing – speeches, news, thank-you notes.
The second half has to talk about a group that the noun belongs to. Sushi is one Japanese dish, so 日本料理 follows; Tokyo is one city, so 都市 follows.
をはじめ has nothing to do with "for the first time". はじめて means that, and をはじめて始めて is the て-form of "start something".
These go beyond をはじめ joining two clauses.
The longer form means the same and sounds a little more formal.