Underway said:
You'll probably find on further research that the element balance is different. The CAF is very army heavy. The Aussies have a much larger Navy (pers wise) than we do. They also operate more aircraft. Also you'll find that the Aussies are the highest paid military in the world. Canada is second (though I can't find the ref where I read that). Cost differences are found there.
I would still assert that they maintain a more robust capability set with significantly fewer people which merits some thought for our own posture. That said, let's do a quick comparison of the full time component:
Canadian Army:22,800
RCN:8,500
RCAF:14,500
Other Commands: 22,200
Total: 68,000
Australian Army: 28,568
RAN:14,215
RAAF:14,120
Total: 56,903
The Army is by far the largest element in both forces (proportionately larger in the Australian Army), but as you say the Australians have clearly emphasized their Navy relative to what Canada has done. That said, the comparison is a bit skewed due to the organic aviation capabilities found within the RAN and Australian Army, and the fact that there is no easy way break out the purple component of the CAF by the environments they support.
To compare the structures of the Armies as an example, there are a lot of similarities:
Canadian Army: 3 Maneuver Brigade HQs, 9 Inf Battalions (6 mech, 3 light), 1 Armored Regiment, 2 Armored Recce Regiments, 3 Arty Regiments, 3 Combat Engineer Regiments, 1 Engineer Support Regiment, and 1 Air Defence Regiment (with no AD equipment).
Australian Army: 3 Maneuver Brigade HQs, 6 Inf Bn (all light), 3 Armoured Cavalry Regiments (each consisting of 1 tank squadron, 1 recce squadron, and an APC squadron providing appx 1 Battalion of lift), 3 Arty Regiments, 3 Combat Engineer Regiments, 1 Engineer Support Regiment, 1 Air Defence Regiment (with equipment), and 1 Aviation Brigade (with dedicated recce, utility, heavy lift and attack platforms).
In this way, they are quite similar to us with the exception of the fact that they maintain 6 infantry battalions compared to our 9. However, with fewer units and perhaps fewer personnel in those units, they generate an equivalent or better capability.
Through the Army Managed Readiness Plan, the Canadian Army force generates a Brigade Headquarters and a single mechanized infantry battle group for sustained expeditionary operations and a much lighter infantry battalion with enablers for a single rotation, risk managed deployment.
http://www.army.forces.gc.ca/assets/ARMY_Internet/docs/en/waypoint-2018.pdf
Through plan Bersheeba, the Aussies rotate each of their three brigades through their high readiness cycle (superficially similar to us), and in each cycle they generate a high readiness capability of a brigade consisting of the equivalent capability of one mechanized battle group, one light infantry battalion, and a surprisingly robust reserve battle group.
http://www.army.gov.au/Our-future/Projects/Plan-BEERSHEBA
http://www.army.gov.au/Our-work/Speeches-and-transcripts/Defence-Reserves-Association-Annual-Conference
Further, they have done that while maintaining anti-armor, infantry mortar, air defence, and attack helicopter capabilities within their Army. Most significantly, their Air Force and Navy have all the capabilities we do, and lots we don't with amphibious lift and airborne EW being two examples that come to mind.
Now the Aussies obviously have a bigger budget than we do, but in terms of how they allocate funds, they are clearly prioritizing capabilities (which implies personnel and equipment in the right combination) over pure personnel strength. The inevitable conclusion here is that we could maintain a broader capability set with the same funding envelope and fewer full time personnel. As I have said, I would love to see some growth in the defence budget, but if we made some hard choices on personnel and procurement (and I appreciate that there is a huge political consideration with that), we could do a lot more with the resources we have.