Gorgotha is a good legendary, once you get him traited. Kerberos was a legendary that my friend used for many levels, because devour was the only way he could compete in higher level GW. It was still random though.
The team I used for many levels early game was Silvermaiden/Ranger/Ranger/Alchemist. Traits that are good to have are Ranger's magic per yellow ally, Alchemist's fire link, and Silvermaiden's reduced skull damage. A replacement for silvermaiden would be Morthani's Will, or your hero with a blue or purple weapon.
I used this team for many levels, probably to about the 150-175 mark. At that point I had gotten The Dragon Soul and Krystenax to drop so I could make a dragon team.
As for PvP Rank 1. At low level, it definitely took me longer as I could only really reliably defeat the 1 or 2 trophy battles. It's still worth the time as the glory you get daily as well as the souls and glory keys you get each rank up help new players! Once you get higher up and can fight the 3 trophy battle, the process becomes quicker.