Building off Ek0nomik's answer of "it depends" -- which is true! -- here's some additional information.
If your internationalized application is ready for localization, prioritization often goes like this:
- European languages such as German, French, Spanish, Italian,
Portuguese (although many go for Brazilian Portuguese first).
- Asian languages such as Chinese, Japanese, Korean (CJK).
- Whatever your user population dictates.
You'll note that leaves a lot out, and that's where "it depends" comes in to play, such as OS usage, relevance to the region, etc. (See also: What languages do you support when localizing?)
The question in your PS is pretty important, and here I'll put a plug in for crowdsourced translation services. I know several open source projects that use services such as Transifex. There are others (search "crowdsourced translation" in Google), and the costs range from some variation of free to monthly fees that might be out of your budget range. However, a quality localization will win you users while a bad localization (relying solely on automatic translators without quality control) will not only not win you any users, it will "win" you negative press.