I don't know about others (I could assume), but I would go Telstra just to get some decent coverage!
I am not gonna start anything here, but work Vodafone wireless connection isn't great, my previous Optus connection was a joke (got decent 3G in the CBD only).
Both my work provided and private Telstra phones get full 3G strength over quite an expansive range of states, cities, towns and in between.
(even out on the water in areas!)
I just hope they will provide me the starter kit without an issue 🙄