japan and austrlia

I would recommend taking a look at Gate 1 travel. It is a travel company with tours, but I find their prices and what they offer for the price to be very good.
I've been on about 6 different tours with them and I plan to use them for Japan in the next year.

You can also see these countries on your own, as they're safe and well organized. I was in Australia in 1996 and Japan in 1997, so I don't have current information. But I do remember that of all the places I've been to by myself, the fact that I went to Australia alone was the most shocking to the largest number of people (despite the fact that they speak English there, and that's it's a fully developed country). My reassurances that it wasn't at all difficult alone were met with disbelief, but I swear it's true - if you can go to Europe on your own, you can go to Australia on your own!

While it's an exaggeration to say that there's lots of English in Japan, there was enough for my needs. And efficiency is their trademark; my sister (who lived there for a while) likes to say Japan is idiot-proof! A train pass can be a very good deal there.

For both countries, while there are various guidebooks, Lonely Planet is particularly good (Australia is their home base).

I've never taken a Gate 1 trip, but most who do seem pleased, as long as you realize it's not a luxury tour. I doubt you'll find any company that visits both countries on a single tour, so you'll need to combine tours.

Another company that goes to both of those locations is Smartours out of New York. I am booked to travel to Turkey and Vietnam (separate tours) in the coming months. Smartours came highly recommended by a family friend, but these are my first tours with them, so I can't give an final opinion yet. I can tell you, however, that the other company I considered was Gate 1. Gate 1 has much better telephone reps when you call in for information and they have dozens and dozens of departure dates. Their prices seem a little lower but are not actually lower because there are quite a few optional tours that you have to shell out additional money for. None of these things made my final choice Smartours, though. The reason I went with Smartours is that I took each hotel for each city for both the Smartours and the Gate 1 and researched them on Tripadvisor. Almost universally, Smartours uses more highly rated hotels, which are usually in the "charming" or "old" part of a city, while Gate 1 uses hotels that are rated moderately well but which are out a bit from where you really want to be as a tourist.

You need to refine your thoughts a bit. It's like asking for a tour company to show you the United States.

Australia is almost as large as the forty-eight contiguous states.

Wakkanai to Naha is close to the distance from San Francisco to Boston.

Tauck Tours, Abercrombie & Kent, and Odysseys Unlimited all offer land-based tours in both countries. All are excellent tour operators. National Geographic, who is also excellent, offers some tours in Australia, not sure about Japan.

If a small ship cruise might be of interest, look at SilverSea or Seabourn, both excellent cruise lines, but you will need to carefully check cities/ports to see if they visit sites you would want to see..

A thing to keep in mind when arranging a tour of Japan: the cultural, architectural (and some would say the spiritual) capital of Japan is Kyoto and nearby historical towns such as Nara, not Tokyo.
What you will see in Tokyo and other major Japanese cities was largely re-built modern with concrete and steel starting in the 1950's, with a few exceptions. This is because most of Tokyo, and other major Japanese cities, were fire-bombed to the ground by the US Air Force [correction, see Ed's comment below: it was the US Army Air Force that fire-bombed Japanese cities.

Kyoto was one of the few locations with great cultural and architectural significance that was spared from the bombing campaign.
This historical fact affects where you may want to go on a tour to this day, 70 years later. Definitely Kyoto and Nara.

Nope. You can't blame that on the Air Force. It didn't exist until 1947.

Ed is correct--it was the United States Army Air Force that fire-bombed Japanese cities.

Army Air Corps

:)

Ed, you're close but I think just a few years too early. See this site:
http://en.wikipedia.org/wiki/United_States_Army_Air_Forces

The last gap in my military knowledge of the whole world since the beginning of time has now been filled.

I was amazed there was even one thing you didn't know about that subject.
Now you know it all.
As I write this, I'm humbly bowing down to the guru.
:)

In all honesty, at least for Japan, it's better to just make your own itinerary and skip the tour group. You can choose where to go, when to go, how long to spend at each place....plus getting around by train is really quite easy and there are signs in English.
If you're just freaked out about being in such a foreign country, the Japan National Tourist Organization has free English speaking guides you can use:

http://www.jnto.go.jp/eng/arrange/travel/guide/list_volunteerGuides_a-n.html