New to Summoner and returning player, where do I start with getting the new summons?

[Alhanelem]

Your avatars, the actual useless pets,

what?

There are also alternatives to the regular avatar quests, called "Trial size trial by ___," which have a lower fame requirement and are intended to be done solo at a lower level. The fights aren't easy for a new player though. Beating them requires that you learn essential summoner soloing skils, mainly kiting (Summon pet, sic on enemy, run away, wait for pet to die, and re-summon before the enemy reaches you).

The regular "high" level fights are easier as they can be demolished in seconds with high level players, but you will have to go through the fame grinding for longer.

After the main 6 elemental avatars, there are a number of others, all of which require story progression:
Alexander and Odin require progress through the Treasures of Aht Urghan storyline (These are really just special summons for your ultimate ability, astral flow)
Atomos and Cait Sith require progress through the Wings of the Goddess storyline
Siren requires completion of the Seekers of Audolin storyline.

[Zenion]

Your avatars, the actual useless pets,

what?

Hah, missed that, I meant to say useful pets. Although, I don't know, some days...