Your question is very broad, but I guess you are looking for inspiration at this point. I would recommend you focus on either the East Coast or the West Coast. There is a whole lot of nothing along the Great Australian Bight (south) and the "Top End" is likely to be a bit harsh and too repetitive for small children.
Here is a suggestion to narrow things down:-
- Watch "Finding Nemo" with your kids before you visit (if it is not too scary)
This will give them something to look forward to and help them understand the trip.
- Fly into Cairns (via somewhere in South East Asia or Japan, depending on how the flights work out)
Visit the Great Barrier Reef. Your children will be able to see fish and coral from a glass bottom boat. 3-4 years old is too young for snorkling unless they and you are very comfortable in the water.
Visit the Daintree Rainforest.
Fly Cairns to Brisbane (as it would be a 1,700 km drive according to google maps)
Travel down the East Coast from Brisbane to Sydney (about 1,000 kms) in a rental car.
There will be plenty to do and you'll have a range of accommodation options along the way. You can visit theme parks, national parks, look for migrating whales etc. Allowing 2 weeks for this would be a relaxed pace. Practically speaking, given you a travelling with small children, you will always be close to a supermarket or at least a petrol station if you need supplies or a stop.
If you wanted to see Outback Australia you would need to deviate from this path further inland. You could consider a visit to Western Plains Zoo Dubbo if you have time. There will be kangaroos. (The first ones you see will probably be dead on the side of the road).
- Spend a couple of days in Sydney
The kids would enjoy the Powerhouse Museum and Luna Park. It's a large city so there are many possibilities.
Uluru as a well known attraction, but it's a long way from anywhere and I doubt your kids will be that impressed. Save that for your next trip.
If you can, avoid the school holidays in NSW and Queensland as this will lessen the number of tourists.