I'd say it a little differently to Jan and whereas November will already be warm with humidity rising in November and the possibility of spring storms further south, the wet season Cairns way is usually wetter from December and often January on and you could risk getting wettest in February/March.

NZ can still be cool, particularly the south island, wet and windy on west coast particularly where it is exposed to the southern ocean whereas the east coast has some protection by the alpine country that runs closer to west coast, the east coast having some plains country but I would not say it would be bitterly cold other than for windchill factor.

Jan describes Feb/Mar. well and they are generally the hottest months for Australia all over though temperatures can start to cool from mid March on depending on annual variations - the TC that has just meandered well offshore fortunately along the north/central Queensland coast for about a week has dropped temperatures quite significantly and a few days after the record Victorian temperatures of 47C there were early morning temperatures in single figures being reported and day temperatures back into mid twenties, a few weeks later and there were reports of snow at altitude.

It'll also make a difference as to whether you're going to do NZ first or last and I think doing it first offers a better option, ie. start in NZ in March and come over to Australia April and by mid April, the wet season will have abated up north but it'll still likely be warm and humid, all that moisture build up tending to make humidity hang about some more so than being there before the wet season.

That said I've known of people from Sydney finding it more than warm enough Cairns way as early as September and people from overseas also finding it a lot warmer than they expected about October/November, given that locals do play it down some - only because as locals they are used to it - a bit like if you live in a warmer climate and go somewhere cooler, you'll likely feel the cold more.

If you are going to do Australia first I would stick with November/December but be prepared to have a changeable pattern of weather for southern Australia can get some enormous spring storm weather just as NQ can get an earlier wet season start, and NZ is renowned for summers starting later and being shorter and so you could be getting some cooler wet weather there, but all up it'll likeably be more comfortable than a Feb/March stint, not overly cold anywhere and not too hot/humid either.

Well it probably depends a little on how well disposed you are to handling cooler weather and as you'd appreciate if a real granny colder weather can make it that you need a bit of mornings warming up, but being a northern hemisphere type you're probably accustomed to that.

I actually prefer the cooler weather a bit more when travelling for it is often more pleasurable being out and about than if it is too warm, and especially if you have humidity to go with it.

It is however something of a hard choice as there is quite a difference between NZ south island and NQ/GBR so I'll give two choices;

1. Australia first and start with GBR sometime towards end of October, getting warmer but mot overly hot then and humidity not so bad and southern parts will have plenty of spring colour and days with some warmth and minimal cooler days.

New Zealand by mid November will also be getting warmer and some good weather.

2. New Zealand first and about mid/late April, weather getting cooler but still not too bad and then over to southern part of Australia with reasonably moderate weather [~20C] and for both countries you should still get something of autumn [fall] colours and then on to NQ late May/early June and you should have missed any real wet weather, it stilling being about mid twenties as far as temps and humidity not too bad.

Of course there are always going to be yearly variations and some greater changes possible if we believe all we're told on global warming and I do not have any sort of a crystal ball.

So do you like all the spring flower blooming, open gardens and flower shows etc. being plentiful, Rhododendrons in the Dandenongs being a trreat - http://www.dandenong-ranges.net.au/ , http://www.visitvictoria.com/displayobject.cfm/objectid.000341F2-2C89-1EBF-BED880C476A90000/ , http://www.parkweb.vic.gov.au/1park_display.cfm?park=49 offering some insights and then you have http://www.royalshow.com.au/competitions.asp about last two weeks of September each year so you could come a bit earlier if that type of year interests and do the south first and then GBR and over to NZ.

And then with the Melbourne Cup Horse Race, world famous on first Tuesday in November, the spectacular roses all about the race course are possibly less talked of but do get plenty of local mention and there'll be open gardens about then too - http://www.abc.net.au/local/stories/2008/10/31/2406559.htm being typical.

Or is it crisper evening airs and the fall colours that attract?, one advantage at least of coming for fall downunder is that you would be returning back above the equator when it'll be warming rather than getting ready for snow if that is to be considered.

Well, all looked to be going reasonably well there Gran with a general consensus it seems on making your trip either late spring/spring-summer or late summer-autumn/autumn.

Until we get colourful and I'm not too sure where the nature's moderate temperatures came from for temperatures mid January on in south of Australia will be approaching peaks.

Cairns in April will still be warm and humid, even possibility still of tropical rain/storms and May/june right through to October is about best time, no gap to exclude June needed.

Seotember on South Island of NZ will still be somewhat wintery.