They couldn't, though, without a lot more difficulty.
You're missing the context that at the time of Rudd's election and the NBN design/build plan, Telstra was actively hostile towards the government. Solomon Trujillo was the CEO at the time, and actively fought against any suggestion that Telstra might be structurally separated (a-la Telecom NZ's split into Chorus and Spark), or be required to build a nationwide wholesale fibre network.
Telstra under Trujillo was the company that famously gave a last minute 13-page (non-compliant) response[1] to a call for bids to build the NBN, that was effectively a giant middle finger to the government.
Forcing a structural separation when the government own a minority stake in the company[2] would've required either re-purchasing it at market rates, or some kind of legislative change, and thus opening the government up to a shareholder lawsuit. At the time, the CAN and Fibre back-haul networks were considered some of Telstra's greatest assets, those would've been some major purchases.
There were a bunch of bad options, but having been backed into this corner by previous government decisions - there wasn't a whole lot they could've done.
[1] https://www.computerworld.com.au/article/270911/telstra_bann...
I do agree with the rest of your comment though.