Which Telco provider is best?

For flying around Australia, there is only one carrier to choose from: Telstra has the greatest coverage. In fact, it is so good that we are often amazed at how far from civilisation you can still get decent coverage at normal GA altitudes. As you go higher, coverage drops because cellular network signals are horizontally polarised; the energy is focused sideways- not upwards

New Zealand has less remote desert, so coverage is generally even better. Check with your telco to see if their cellular coverage is sufficient for your needs.

How Much Data Does AvPlan need?

Downloading all the Charts, ERSA, DAPs and other required data with every update, you would not use much more than about 6 GB per year for Australia, and 1.5 GB per year for NZ.

While you are flying and all data is downloaded, you will be using very little indeed. The data requirement for e.g. METAR and Traffic updates and the like is very small.

As you will most likely download all of the chart data at home on WiFi, you do not need a huge amount of data on your plan.

These days, even a "small" data plan is likely to be sufficient.