Learn Portuguese (Portugal): Ela arranjou um emprego novo na cidade.

Arranjar is the most natural and common verb in everyday Portuguese for finding or managing to get something, like a job or an item. Conseguir focuses more on the effort to overcome an obstacle (succeeding in getting it), while obter is much more formal and translates closer to obtain.

Would the meaning change if it said um novo emprego instead of um emprego novo?

There is a subtle difference. Placing the adjective after the noun (um emprego novo) technically emphasizes that the job itself is brand new, perhaps a newly created role. Placing it before the noun (um novo emprego) implies a new job for her, or simply another job. In casual speech, however, native speakers often use them interchangeably in this context.

Could I use trabalho instead of emprego here?

Yes, but there is a slight nuance. Emprego specifically refers to formal employment or a paid position. Trabalho is the broader concept of work, labor, or a task. While you can say arranjar um trabalho, arranjar um emprego is the most precise and common way to say someone got hired for a formal position.