Bonus points if the API can retrieve balances for multiple addresses at once.
That seem more of a benefit than a problem, at least to me. I see no better way that the information could be served from a REST API. I glanced at the documentation for the API you linked to and it seems that it could work for OP. My only concern with it is the rather limiting quota that each API key is assigned (no more than 1 query every 10 seconds). Depending on how many coins OP needs to obtain address information for, this method could potentially be too slow for his purposes since because of the nature of the API, at least one query is required per coin, but it does seem like the most convenient method. The only alternative is to find different APIs for each coin and use those so that the different blockchains don't have to be stored on the machine, but that is all that I can really think of.