Learn Hardcore Indonesian: Teman saya baru berkenalan dengan pacar barunya belakangan ini. - My friend has recently gotten acquainted with her/his new partner.

baru before berkenalan is an adverb meaning “just / only recently” (has just gotten acquainted).
In pacar barunya, baru is an adjective meaning “new” (new boyfriend/girlfriend), and -nya marks “his/her” or “the.”

Is it redundant to say both baru and belakangan ini?

It’s not wrong; it adds emphasis to recency. You can keep both for clarity or drop one:

Keep both (strong emphasis): Teman saya baru berkenalan … belakangan ini.
Drop the adverbial: Teman saya baru berkenalan dengan pacar barunya.
Drop baru (milder): Teman saya berkenalan … belakangan ini.

What exactly does berkenalan mean? How is it different from kenal, memperkenalkan, and dikenalkan?

berkenalan (dengan X): to get acquainted (reciprocal-ish), “meet and get to know.”
kenal (dengan X): to know/be acquainted (state), e.g., Saya kenal dia = I know him/her.
memperkenalkan (X kepada Y): to introduce X to Y (active/causative).
dikenalkan/diperkenalkan (kepada/dengan X): to be introduced to X (passive). So your sentence says the friend themselves got acquainted, not that someone introduced them.

Why is dengan used after berkenalan? Can I use sama?

berkenalan typically takes dengan. In informal speech, sama is common and natural:

Formal/neutral: berkenalan dengan
Informal: kenalan sama Avoid berkenalan pada; it’s not idiomatic with people.

Does berkenalan mean “to start dating” here?

Not literally. berkenalan is “to become acquainted/meet.” If you mean “start dating,” use:

baru jadian (just became a couple)
mulai pacaran (started dating) Example: Teman saya baru jadian belakangan ini.

Who does -nya in barunya refer to?

-nya is a third-person marker: “his/her/their” (singular, gender-neutral) or sometimes “the.” In this sentence, it most naturally refers to teman saya. If there is another previously mentioned person, context decides. To be explicit:

pacar barunya teman saya (my friend’s new partner)
pacar baru dia / pacar barunya dia (his/her new partner)

Why is -nya attached to baru instead of pacar in pacar barunya?

Clitic possessives (-ku, -mu, -nya) attach to the end of the whole noun phrase. Since the noun phrase is pacar baru, the clitic goes on the last word: pacar baru-nya → pacar barunya. Compare:

rumah besar → rumah besarnya (his/her big house)
teman baik → teman baiknya (his/her good friend)

What’s the difference between pacar baru and pacar barunya?

pacar baru = “a new boyfriend/girlfriend” (indefinite, not tied to a specific possessor unless stated)
pacar barunya = “his/her new boyfriend/girlfriend” (or “the new boyfriend/girlfriend [already known in context]”)

How do I specify boyfriend vs girlfriend, since pacar is gender-neutral?

Add a gendered word if needed:

Boyfriend: pacar laki-laki, pacar cowok (informal)
Girlfriend: pacar perempuan, pacar cewek (informal) More formal alternative to pacar: kekasih (lover/partner, literary/formal).

Can I say Temanku instead of Teman saya? Is there a register difference?

Yes:

Teman saya = my friend (neutral–formal)
temanku = my friend (neutral; clitic -ku) Colloquial variants: temen saya, temen gue (Jakarta-style informal; gue = I/me). Pick pronouns consistently for the register you want.

Can belakangan ini go at the beginning?

Yes. Fronting the time phrase is common:

Belakangan ini, teman saya baru berkenalan dengan pacar barunya. Comma optional but helps readability.

Does Indonesian mark past tense here?

Indonesian doesn’t conjugate for tense. Recency is shown by time words:

baru (just/recently)
belakangan ini (lately) Without them (Teman saya berkenalan …), the time is vague and depends on context.

Can I omit dengan and say berkenalan pacar barunya?

No. berkenalan needs a preposition before the person: use dengan (neutral) or sama (informal).

What’s the nuance difference among belakangan ini, akhir-akhir ini, and baru-baru ini?

belakangan ini: lately/these days (broad, ongoing period).
akhir-akhir ini: in recent times (often suggests a streak or repeated occurrences).
baru-baru ini: recently (a specific recent occasion/event).

Can I use barusan or baru saja instead of baru?

Yes, both heighten the “just now” feel:

barusan (very recent, informal): Teman saya barusan berkenalan …
baru saja (neutral): Teman saya baru saja berkenalan … Plain baru is flexible and slightly less immediate.

If I want to say “My friend was introduced to his/her new boyfriend/girlfriend,” how do I phrase it?

Use a passive with (di)perkenalkan:

Teman saya baru diperkenalkan kepada pacar barunya. You’ll also hear diperkenalkan dengan, though many prefer kepada with people.