Yeah, Im sure that rabbit proof fence can also stop any armies
I dont know what is really sooooo realistic about this map. Comparing it to the first one you posted, the single thing that looks the same is the continents positions, because many many countries are now different... This is good, because we all can see you are interested in playability, but so you talk you will not make any major changes? Maybe you are going too fast, mate...
About the continents: (countries, borders, routes)
Western Australia (8, 5, 5). 5 borders are too much, I believe, but this is simple to solve, its only to remove Nullabor Plain border to Coober. Bonus of 5 at maximum. Hmmmm, "Great Victoria Desert"... what a great name, lol. Couldnt it be just Victoria Desert? Same to Sandy...
Queensland (8, 4, 6)... well, maybe you could move the connection to Western Australia to Brisbane and reduce a border here too, its an idea... by the way, the label "X to Y link" is not necessary, and its ugly too. Bonus of 5 too...
South Australia (5, 3, 5... or 4 if you remove Nullabor). Its playable, bonus of 3. But I just dont understand why you changed the real borders of the original map...
New South Wales (5, 4, 4). 4 borders in 5 countries isnt good, maybe one less border... You can think a better way to do it, Im sure. Bonus of 3.
N. Territory (4, 2, 6). Classic, bonus of 2
Victoria (4, 2, 4). Same, bonus of 2.
About the map playability:
It increased a lot... but its a bit strange... we have 3 groups of twin continents, lol. More important is to realize there are 2 big continents and 4 small ones, all connected... and Victoria is by far the most powerful area, since it can directly prevent other 2 small continents of being taken... and NT can be attacked from big continents, where people can possibly fortify and have bigger armies... beyond this, its a direct link from one big to the another one (maybe you can use better the original borders, making this different, and making the lake the fastest passage). In fact, I would try to decrease the power of Victoria a bit.
And only to confirm, you want a small Australia map, 36 countries, correct? Hmmm, maybe using a bigger size we could make some things different, you can think about it.
About visual:
I think you can remove the link label, and put the legend to the west, so we can avoid some wasted space... anyway, there will still be some space to something...
We can think about a different ocean, too, but its not really needed... but please try a different font, I dont like too much this one you are using... its very simple, it adds no appeal.