How much of a fuss is it for a start-up fresh out of YC to hire someone on an E-3 visa (the one for Australians) ? i.e., time & cost of the process including legal advice & applying for licences if any
Super cheap, easy, and fast. The E-3 visa is the easiest visa to get (as long as the applicant is Australian of course) and it doesn't matter whether the employer is a startup or an established large company.